리스트(List)

 

데이터를 1열로 나열

 

🟩 접근 어려움

흩어져서 저장되어 있기 때문에 포인터를 처음부터 순서대로 따라가야만 원하는 데이터에 접근 가능

 

🟩 추가, 삭제 용이

추가시 추가할 위치의 앞뒤 포인터만 변경하면 된다.

삭제도 동일

 

cf. 삭제시, 메모리에는 데이터가 남지만 어디에도 접근할 수 없으므로 일부러 삭제할 필요없다.

이후에 이 영역이 다시 사용될 때 덮어쓰여 재사용 가능하다.

 

🟩 데이터가 메모리 사이의 연속된 위치에 저장되지 않는다

데이터의 물리적인 순서와 관련없음

연결 정보의 논리적 순서를 결정한다.

 

🌟 head

시작점, 선형 구조에서 첫 번째 노드를 가리키는 용어

노드(node) = data + pointer

전체 리스트를 탐색하거나 데이터 추가/삭제시 기준점으로 사용한다.

 

🟩 계산시간

검색 O(n)

추가/삭제 O(1)

 

🟩 크기 변경에 유연하다

필요에 따라 동적으로 할당하여 효율적인 메모리 할당이 가능하다.

---

🌟 원형 연결 리스트 (순환 리스트)

리스트의 마지막 데이터가 선두를 가리키도록 한다.

선두, 후미의 개념이 없다.

 

 

🌟 양방향 리스트 (이중연결 리스트)

포인터를 2개 사용해서 앞뒤 데이터를 가리킨다. 편리하다.

이 때 head는 list의 시작, 끝을 모두 나타낼 수 있으며 삽입과 삭제에 용이하다.

 

cf. 포인터 수가 늘어나므로 데이터 저장을 위한 영역이 많아지는 단점이 있다.

데이터 추가, 삭제 시 변경해야할 포인터가 늘어난다.