연결 리스트 - Linked List

■ 잡담

Linked List의 장단점이 무엇입니까? 면접관님의 질문이였습니다. 지원자는 그 순간 머리를 재빠르게 굴리기 시작했지만 시원한 답변을 하지 못했습니다. 지원자는 Linked List의 구조를 숙지하고는 있었지만, 장단점에 대해서는 인지를 하고있지 못했기 때문입니다. 이번 포스팅에서는 이와같은 불상사가 발생하지 않기 위해 Linked List를 이해하고 그의 장단점에 대해 알아보도록 하겠습니다.

■ 단일 연결 리스트

연결 리스트는 각각의 노드가 다음 노드를 가리키며 연결되어 있기 때문에 연결리스트라고 합니다. 단일 연결 리스트의 경우에는 각 노드가 다음 노드만을 가리키기 때문에 단일 연결리스트라고 불립니다. 단일 연결리스트에 대한 정확한 이해는 그림을 통해 확인해 보도록 하겠습니다.

단일연결리스트는 노드로 구성되어 있습니다. 각각의 노드는 데이터(하늘색)와 다음 노드의 주소값(파란색)을 가지고 있습니다. 노드1은 노드2의 주소값을 가지고 있고, 노드2 는 노드5의 주소를 가지고 있습니다. 노드5는 마지막 노드이기 때문에 아무런 노드의 주소를 가지고 있지 않습니다.

 ◆ 배열 VS 연결리스트

위의 그림을 통해 연결리스트의 장점을 알 수 있습니다. 배열의 경우 아래 그림과 같이 고정된만큼의 공간을 할당받고 순서대로 할당받은 공간을 사용해야 합니다.

그림 - 배열

하지만 연결 리스트의 경우 각 노드들의 주소값들이 연결되면 되기 때문에 메모리가 필요할 때 마다 할당을 받아 연결시켜 주면 됩니다. 따라서 연결 리스트를 사용하게 되면 컴퓨터의 전체 메모리가 허락하는 한 계속해서 자료를 저장할 수 있습니다.

 ◆ 단일 연결리스트의 노드 삽입

 단일 연결리스트에 새로운 노드를 삽입하는 과정입니다.

가장 처음으로 추가하고자 하는 노드에게 앞 노드가 가지고 있던 주소값을 주고 그 앞 노드에는 새롭게 추가하려는 노드의 주소를 주면 됩니다. 이해가 잘 안가신다면 위의 그림을 통해 이해하시면 될것 같습니다.

■ 이중 연결리스트

이중연결리스트 역시 노드간에 주소값을 통해 연결되어있는것은 같습니다. 하지만 하나의 노드가 가리키는 노드의 주소값이 2개라는 점이 단일 연결리스트와는 다른점 입니다.

그림을 보면 알 수 있듯이 각각의 노드가 자신 뒤의 노드 뿐만 아니라 앞의 노드도 가리키고 있습니다. 따라서 이중 연결리스트는 데이터를 탐색하는대에 있어서 단일 연결리스트보다 유리하며, 노드의 추가 삭제가 효율적입니다.

 ◆ 이중 연결리스트의 노드 삽입

 이중 연결리스트에 새로운 노드를 삽입하는 과정입니다.

■ 환형 연결리스트

환형(원형)연결 리스트는 시작노드와 끝 노드가 연결되어 있어 순환하는 연결리스트 입니다. 환형연결 리스트는 다른 연결리스트와는 다른 강점이 있습니다.

다른 연결 리스트같은 경우에는 마지막 노드를 찾기 위해서 처음노드부터 탐색해야 했습니다. 하지만, 환형 연결리스트 같은 경우는 위의 그림과 같이 처음 노드와 마지막 노드가 연결되어 있으므로 마지막 노드를 찾기위해서 처음부터 탐색할 필요가 없습니다.

하지만 환형 리스트만의 강점이 있는 반면 단점도 존재합니다. 연결 리스트가 원형으로 연결되어 있기 때문에 무한루프에 빠지는 것을 유의해야 하며 처음 노드를 잘 기억해 놓고 무한루프를 방지해 주어야 합니다.

■ 마무리

링크드리스트(연결리스트)는 설명만 봐선는 잘 이해가 되시지 않을 수도 있습니다. 따라서 연결리스트를 한번쯤 코드를 짜는 연습을 해보는것이 좋을것 같습니다. 이에 대한 내용은 다음 포스팅에서 진행하도록 하겠습니다.