자료구조 04 : 링크드 리스트 (linked list)

배열이 미리 연결된 특정한 공간을 예약을

해놓고 거기에 데이터를 쓰고 읽는 구조라면,

링크드 리스트는 미리 예약을 해놓지 않고

필요할 때마다 데이터를 추가할 수 있는 구조다.

배열의 단점을 극복한 자료구조라고 할 수 있다.

 

 

링크드 리스트 구조

(데이터+다음 데이터를 가리키는 주소(포인터))

가 하나의 데이터로 이걸 노드(Node)라고 한다.

여기서 각 노드 안에 다음/이전 노드와의 연결

정보를 가지고 있는 공간을 포인터라고 한다.

 

노드마다 다음 노드의 주소가 있기 때문에

첫번째 노드만 알면 꼬리물기 식으로 추적해

원하는 노드의 값을 알아낼 수 있다.

그렇기 때문에 꼭 이어져있는 주어진 공간이

아닌 원하는 곳곳에 노드 생성과 추적이 가능하다.

물론 첫번째 노드 주소를 알고 있고,

노드들이 연결되어 있다는 전제 하에!

 

장점 : 미리 데이터 공간을 할당하지 않아도 됨.

단점 : 연결을 위한 별도의 공간을 필요로 하기

때문에 저장 공간 효율이 높지 않다.

같은 맥락으로 연결 정보를 찾는 시간이 필요

하기 때문에 접근 속도가 느리다. 또한 중간에

있는 데이터를 삭제한다면 앞뒤 데이터의 연결을

재구성해야하는 추가 작업이 필요하다.

 

 

다양한 링크드 리스트 구조

더블 링크드 리스트 (Doubly linked list)

• 이중 연결 리스트라고도 함
• 양방향으로 연결되어 있어 노드 탐색이 양쪽으로 모두 가능 (tail 존재)
• 기존의 앞에서부터 순차적으로 갈 수밖에 없는 링크드 리스트의 단점을 보완한 형태
• [이전 주소|현 노드|다음 노드 주소] 노드 구성을 가짐
• 단점 : 매우 복잡함...ㅠ