[자료구조] 연결리스트(LinkedList)

연결리스트란?

연결리스트 : 데이터 요소들을 노드(Node)라는 단위로 구성하여 메모리 상에서 연속적으로 배치되지 않고, 각 노드들이 포인터(Pointer)로 연결되어 있는 자료구조

• 각 노드는 데이터를 저장하는 데이터 필드(data field)와 다음 노드를 가리키는 링크 필드(link field)로 구성되어 있다

단방향 연결리스트(Singly Linked List) : 각 노드가 다음 노드를 가리키는 링크 필드만을 갖고 있다. 이러한 구조로 인해 단방향으로 노드들이 연결되어 있다.

양방향 연결리스트(Doubly Linked List) : 각 노드가 이전 노드와 다음 노드를 가리키는 링크 필드를 갖고 있다. 양방향으로 노드들이 연결되어 있기 때문에 양쪽 방향으로 노드를 탐색할 수 있다.

 

연결리스트의 장단점

장점

1. 동적 크기 : 런타임 중에 크기를 동적으로 조정할 수 있다. 따라서 데이터 요소들을 삽입하거나 삭제할 때 메모리의 재할당이 필요하지 않다.

2. 삽입과 삭제의 효율성 : 해당 노드의 포인터만 변경하면 되기 때문에 배열과 달리 데이터를 이동시키지 않아도 된다. 예를 들어, 노드A와 노드B가 있을 때 A가 B를 가리키고 있다고 가정하고, 노드C를 A다음에 추가할 때, A의 포인터가 C를 가리키도록, C의 포인터가 B를 가리키도록 해주면 된다.

3. 메모리 관리 : 동적으로 메모리를 할당하고, 각 노드가 독립적인 메모리 공간에 할당되기 때문에 연속적인 메모리 공간을 요구하지 않으며, 이로 인해 메모리 공간의 낭비를 줄일 수 있다. 

단점

1. 임의 접근이 어려움 : 각 노드들이 연속된 메모리 공간에 저장되지 않기 때문에, 특정 노드로 접근하는 데에는 선형 시간이 소요된다. 즉, 시작 노드에서 떨어져 있는 만큼 시간이 걸린다.

2. 추가적인 메모리 사용 : 각 노드는 데이터와 다음 노드를 가리키는 포인터로 구성되어 있기 때문에, 배열과 비교했을 때 추가적인 메모리를 사용한다.

3. 역방향 순회의 어려움 : 단일 연결리스트는 다음 노드만을 가리키기 때문에 역방향으로 순회하려면 추가적인 작업이 필요하다.

 

연결리스트를 사용하면 좋은 경우

• 동적 크기 필요 : 데이터의 크기가 동적으로 변하는 경우, 연결리스트는 크기 조정이 용이하여 메모리를 효율적으로 관리할 수 있다. 예를 들어, 사용자가 입력한 데이터를 저장하는 경우, 연결 리스트를 사용하면 필요에 따라 새로운 노드를 동적으로 할당하여 저장할 수 있다.

• 삽입과 삭제가 빈번한 경우 : 삽입과 삭제가 빈번한 작업에서 연결리스트는 노드의 포인터만 변경하면 되기 때문에 간단하게 작업을 수행할 수 있다. 예를 들어, 작업 목록에 작업을 추가하거나 제거하는 경우, 연결리스트를 사용하면 효율적으로 관리할 수 있다.

예시: 은행의 대기열 관리 시스템은행에 도착한 고객들을 대기열에 추가하고, 고객이 서비스를 받으면 대기열에서 삭제하는 동작이 빈번하게 발생한다. 이때, 연결리스트를 사용하면 새로운 고객을 대기열의 맨 뒤에 추가하거나, 서비스를 받은 고객을 대기열에서 제거할 때 단순히 링크를 변경해주면 되기 때문에 효율적이다.

 

연결리스트를 사용하면 좋지 않은 경우

• 임의 접근이 빈번한 경우 : 연결리스트는 각 노드가 포인터로 연결되어 있기 때문에 이 경우 접근이 느리다. 따라서, 임의 접근이 빈번한 경우에는 배열이나 해시 테이블 등의 다른 자료구조를 고려하는 것이 좋다. 

• 메모리 접근 속도가 중요한 경우 : 연결리스트는 데이터에 접근할 때 포인터를 따라가야 한다. 이는 메모리 접근 속도를 느리게 만들 수 있다. 

예시: 주소록 관리

주소록은 개별적인 연락처들로 구성되며, 사용자는 특정 연락처를 이름으로 검색하거나 원하는 순서로 정렬할 수 있어야 한다. 이런 경우에는 랜덤 접근이 필요하고, 연결리스트는 순차적으로 접근해야 하기 때문에 효율적이지 않다. 따라서, 배열이나 트리와 같은 자료구조가 주소록 관리에 더 적합하다.