[자료 구조] 리스트(List)란?

안녕하세요! 오늘은 자료 구조인 리스트에 대해서 공부해보겠습니다.

자료 구조에 관한 첫번째 글인데 두근두근합니다.

---

리스트란

리스트는 가장 기본적인 선형 자료 구조로 데이터의 추가/삭제가 용이하다는 장점이 있습니다.

동작 방식을 알아두면 굉장히 유용합니다 👍

시스템의 규모가 커질수록 리스트의 세부적인 구현 사항들을 하나하나 신경써야 합니다.
지금은 "그래야 할 수도 있다" 정도로 알아두고, 나중에 꼭 챙겨봐요!

 

특징

리스트의 가장 큰 특징이 뭘까요?

 

크기가 정해져 있지 않다!

데이터 추가!

데이터 삭제!

요소를 자유롭게 추가하고, 삭제할 수 있다는 것이 리스트의 가장 큰 특징입니다.

 

위에서 예시로 든 그림에서는 리스트의 끝에 위치한 데이터만 추가/삭제할 수 있는 걸로 보이지만

실제로는 데이터를 원하는 위치에 추가할 수도 있고, 삭제할 수도 있습니다.

 

구현 방법

그러면 이런 기능을 만족하는 리스트를 어떻게 구현할 수 있을까요?

널리 알려진 방법으로는 1) 배열을 이용한 리스트 구현, 2) 포인터를 이용한 연결 리스트 이 있습니다.

 

일반적으로 배열을 이용하여 구현한 리스트는 데이터 조회가 많은 경우에 성능이 좋고,

포인터를 이용한 연결 리스트는 데이터 추가/삭제가 많은 경우에 성능이 좋습니다.

 

그림을 이용해서 설명해볼까요?

 

배열을 이용한 리스트 구현

처음 리스트를 생성할 때, 임의의 크기의 배열을 할당하고 데이터를 추가하다가 할당된 배열의 사이즈보다 커지면 다시 배열을 할당합니다.

배열을 이용하여 구현한 리스트에서 데이터 추가!

미리 할당받은 배열이 꽉 찼을 때의 데이터 추가!

 

6번째 데이터에 접근하고 싶으면 할당 받은 배열들의 사이즈를 알고 있으니 빠르게 접근할 수 있습니다.

 

하지만 중간에 있는 데이터를 삭제하면 그 다음 데이터들을 하나씩 차곡차곡 전부 옮겨줘야 합니다...

데이터 크기가 클수록 시간이 오래 걸리겠죠?

 

포인터를 이용한 연결 리스트 구현

리스트를 생성하면 첫번째 요소의 포인터가 반환됩니다.

포인터를 이용한 리스트의 데이터 추가!

5번째 데이터에 접근하고 싶으면 리스트의 첫번째 데이터부터 순회하면서 5번째 데이터까지 도달해야 합니다.

이렇게 보면 비효율적으로 보일 수 있지만 데이터 추가/삭제에 부가적인 비용이 필요 없습니다!

 

---

리스트에 대해서 간단히 공부해봤는데 어떠신가요?

부족한 부분 알려주시면 보완하도록 하겠습니다! 같이 열심히 공부해봐요 :)