CWN(CHANGE WITH NEWS) - 자료구조 어디까지 알고 있니? #2. 연결리스트의 3가지 종류

단순 연결 리스트(Singly Linked List)
단순 연결 리스트는 각 노드에 하나의 포인터 영역을 가지고 있는 연결리스트를 말한다. 가장 단순한 형태이면서 동시에 가장 많이 사용되는 구조이다.

헤드 노드를 참조하는 주소를 잃어버렸다면, 데이터 전체를 쓸 수 없게 된다. 또, 노드를 참조하는 주소 중 하나가 잘못되어도 체인이 끊어진 양부터 뒤쪽자료들을 유실한다. 따라서 안정적인 자료구조는 아니다.

이중 연결 리스트(Doubly Linked List)
단순 연결 리스트에서는 각 노드가 다음 노드를 가리키고 있지만, 이전 노드를 가리키지 않아 이전 노드로 접근할 수가 없다. 단순 연결 리스트의 제한점을 해결한 구조가 이중 연결 리스트이다.

리드를 전방 혹은 후방의 양방향으로 탐색이 가능하고 노드의 삽입이나 삭제가 쉽다는 장점이 있다.

원형 연결 리스트(Circular Linked List)
단순 연결 리스트에서 마지막 원소가 널 대신 처음 원소를 가리키게 하면 원형 연결 리스트가 된다. 이와 비슷하게 이중 연결 리스트의 처음과 끝을 서로 이으면 이중 원형 연결 리스트를 만들 수 있다.

스트림, 버퍼의 구현에 많이 사용하며 이미 할당된 메모리 공간을 삭제하고 재할당하는 부담이 없기 때문에 큐를 구현하는 데에도 적합하다.

이번 기사에서는 연결리스트의 종류에 대해 알아봤다. 다음 기사에서는 스택, 큐, 덱에 대해 알아보자.

[저작권자ⓒ CWN(CHANGE WITH NEWS). 무단전재-재배포 금지]