연결리스트(Linked List)

연결리스트(Linked List)는 링크드리스트라고도 부릅니다. (사실 저는 링크드리스트라고 더 자주 말합니다.)

어쨌던, 링크드리스트는 데이터와 포인터를 갖고 있는 노드들이 포인터로 연결되어있는 자료구조입니다.

그림으로 보면 쉽게 이해할 수 있으니 이미지를 첨부하겠습니다.

head라는 글자가 가르키고 있는 노드가 있고, 이 노드에서 화살표가 나와 다음 노드를 가르킵니다. tail의 노드는 null을 가르키고 있습니다. 구조가 이해되시나요?

링크드리스트는 노드로 이루어져 있으며 이 노드들은 Data부와 Pointer부로 구별되어 있습니다.

Data부에는 노드의 데이터가, Pointer부에는 다음 노드를 가르키는 포인터만이 적재될 수 있습니다.

또한 head 포인터의 노드와 tail 포인터의 노드가 존재합니다. 이 노드들에는 포인터만을 연결하며 데이터를 담지 않습니다. 그 이유는 헤드노드와 테일노드에 데이터를 담게 되면 노드의 삽입이나 삭제시에 작업이 훨씬 복잡해지기 때문입니다.

배열의 경우 크기가 고정적이므로 50의 인덱스만큼 사용하던 배열을 60개까지 사용하고 싶다면 메모리를 재할당하여 사용해야 합니다. 또한 중간에 삽입이나 삭제연산을 하고싶을 경우, 그 뒤의 모든 요소들을 한 칸씩 당기거나 밀어주는 O(n)의 연산이 필요합니다.

그러나, 연결리스트는 리스트의 길이가 가변적이므로 삽입과 삭제가 빈번하게 일어나는 상황에서 사용하면 효과적입니다.

삽입과 삭제가 빠른 이유는 노드간의 연결이 포인터로 구현된 참조링크의 형태이기 때문입니다.

만약 중간에 있는 노드를 삭제하거나, 중간에 노드를 삽입한다면 삽입하려는 위치의 이전노드와 이후노드의 포인터만 바꾸어주면 됩니다. 이러한 방법으로 쉽게 삽입과 삭제를 할 수 있습니다.

링크드리스트의 추가 개념으로 이중연결리스트와 원형연결리스트가 존재합니다.

1. 이중 연결리스트

이중 연결리스트는 기존의 다음 노드만 가르키고 있는 노드들의 Pointer부에 이전 노드를 가르키는 정보를 추가하여 구현하는 것입니다. 현재 노드의 이전 노드들을 탐색하는 상황이 발생할 때 사용할 수 있습니다.

2. 원형 연결리스트

원형 연결리스트는 원형 큐처럼 순환하는 형태로 연결리스트를 구현하는 것입니다. 마지막 tail노드의 next가 null이 아닌 head를 가리키게 되어 순환하는 형태로 탐색할 수 있습니다.