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

첫번째로 알아볼 자료구조는 리스트다.

 

리스트는 코딩을 공부하면서 string, int 다음으로 많이 사용한 것 같은데 그냥 일렬로 있다는 생각만 해보고 구체적인 구조에 대해 생각해본적이 없는데 이번 기회에 알고 넘어가야겠다.

 

현재 차근차근 해보자는 생각에 기초적인 부분을 공부하고 있다. 좀 더 구체적인 내용은 다른 글에 작성하거나 추후 글을 수정하는 방향으로 해보겠다.

틀린 내용이 있거나 궁금한게 있다면 편하게 댓글 남겨주시면 감사하겠습니다.

---

📌 개념

리스트는 데이터를 일직선으로 줄줄이 정렬할한 데이터 구조이다.

데이터의 추가나 삭제는 쉬운 반면, 원하는 데이터에 접근하는 시간은 오래 걸린다.

 

리스트의 개념도

리스트에 각 Blue, Yellow, Red가 저장되어있고, 각 데이터는 포인터를 가지고 있어 다음 데이터의 메모리 주소를 가르킨다

각 데이터는 메모리상에 연속된 공간에 있을 필요 없다. 포인터만 다음 데이터를 잘 가르키고 있으면 된다.

 

데이터 접근

이러한 리스트에서 특정 데이터를 접근하려면 데이터의 포인터를 따라 찾아가야한다.

이를 순차 접근 혹은 시퀀셜 액세스(sequential access)라고 한다.

 

예를 들어 Red에 접근하고 싶다면 Blue에 먼저 접근하고 이후 Yellow를 거쳐야지만 Red에 접근할 수 있다.

 

데이터 추가

반면 데이터를 추가하는건 쉽다. 만약 Green을 추가하고 싶다면

데이터 추가2

 

Blue의 포인터를 Green으로 옮겨주고 Green의 포인터를 Yellow로 가르키면 데이터 추가는 끝이다.

 

데이터 삭제

삭제는 더 간단하다. Yellow를 삭제하겠다는 가정하면 Yellow를 가르키는 Green의 포인터를 그 다음 순서인 Red를 가르키게 하면 된다.

데이터 삭제

⏱️ 시간복잡도

리스트에 저장된 데이터의 개수가 n개라면

데이터에 접근할 때 마지막 있는 데이터를 생각하면 총 n번의 시간이 걸리기 때문에 O(n)이 된다.

데이터를 추가하거나 삭제할 때는 데이터의 개수에 영향을 받지않고 포인터만 변경하면 되기 때문에 O(1)이 된다.

---

📌 추가 내용

기본적인 리스트이 경우 마지막에 포인터가 없다.

마지막에 데이터의 포인터가 맨앞의 데이터를 가르키게 하면 리스트를 고리 모양으로 연결할 수 있다.

이를 원형 리스트 혹은 순환 리스트라고 한다.

순환 리스트

이렇게 하면 데이터의 맨 앞이나 맨 뒤라는 개념은 사라진다. 이러한 리스트는 항상 일정한 개수의 최신 데이터를 보관해야하는 상황에서 사용된다.

그리고 기본 리스트의 경우 각 데이터의 포인터가 하나인데, 각 데이터가 포인터 두개를 앞뒤로 가르키게 만든 양방향 리스트도 있다

양방향 리스트

리스트를 앞에서 뒤로는 물론 뒤에서 앞으로도 검색할 수 있다.

다만 양방향 리스트는 포인터 수가 늘어난 만큼 데이터의 양이 증가하고, 데이터를 저장하기 위한 공간도 늘어난다는 단점이 있다.

 

---

참고 자료

그림으로 이해하는 알고리즘 : 이시다 모리테루, 미야자키 슈이츠

 

 

 

배열 vs 리스트는 배열 포스팅 📌추가내용에 있어요! 

https://twd0622.tistory.com/9

[자료구조] 배열 (Array)