연결 리스트(Linked List)

연결 리스트(Linked List)는 데이터 항목들이 노드(Node)라는 요소에 저장되며, 각 노드가 다음 노드를 가리키는 포인터(Pointer) 또는 참조(Reference)를 통해 서로 연결되어 있는 선형 데이터 구조입니다. 연결 리스트는 배열과 비교했을 때, 동적 크기 조정이 용이하고, 삽입과 삭제 연산이 더 효율적일 수 있습니다. 다만, 임의 접근(Random Access)이 불가능하여 특정 인덱스의 요소에 접근하기 위해서는 처음부터 해당 요소까지 순회해야 합니다.

연결 리스트에는 주로 다음과 같은 종류가 있습니다:

1. 단일 연결 리스트(Singly Linked List):
   •     각 노드가 다음 노드만을 가리키는 포인터를 가지고 있습니다. 따라서 리스트를 한 방향으로만 순회할 수 있습니다.
2. 이중 연결 리스트(Doubly Linked List):
   •     각 노드가 이전 노드와 다음 노드 양쪽을 가리키는 포인터를 가지고 있어, 리스트를 양방향으로 순회할 수 있습니다.
3. 원형 연결 리스트(Circular Linked List):
   •     단일 연결 리스트나 이중 연결 리스트의 마지막 노드가 첫 번째 노드를 가리키도록 설정되어 있어, 원형으로 순회할 수 있습니다.

연결 리스트의 기본 구조

[노드1] -> [노드2] -> [노드3] -> ... -> [노드n] -> null

• 노드(Node): 데이터와 하나 또는 두 개의 포인터(next, prev 등)를 포함합니다. 데이터는 해당 노드가 저장하는 값이며, 포인터는 리스트의 다른 노드를 가리키는 데 사용됩니다.
• 헤드(Head): 리스트의 첫 번째 노드를 가리킵니다.
• 테일(Tail): 리스트의 마지막 노드를 가리킵니다. 이중 연결 리스트와 원형 연결 리스트에서 주로 사용됩니다.
• null: 단일 연결 리스트와 이중 연결 리스트에서 마지막 노드의 next 포인터가 가리키는 값으로, 리스트의 끝을 나타냅니다.

연결 리스트의 장점과 단점

장점:

• 동적 메모리 할당: 배열과 달리, 연결 리스트는 실행 시간에 크기를 조정할 수 있어 메모리를 효율적으로 사용할 수 있습니다.
• 삽입과 삭제 연산이 효율적: 특정 위치에 노드를 삽입하거나 삭제할 때, 해당 노드의 포인터만 수정하면 되므로 상대적으로 빠르고 간단합니다.

단점:

• 임의 접근 불가: 배열처럼 인덱스를 통한 빠른 접근이 불가능하여, 특정 요소에 접근하기 위해서는 리스트를 순회해야 합니다.
• 추가 메모리 사용: 각 노드가 데이터 외에 하나 이상의 포인터를 저장해야 하므로, 추가적인 메모리 공간이 필요합니다.

연결 리스트는 그 구조적 특성 때문에 다양한 알고리즘과 자료 구조에서 유용하게 활용됩니다. 예를 들어, 스택(Stack), 큐(Queue), 해시 테이블(Hash Table)의 충돌 해결 메커니즘 등에서 연결 리스트가 사용됩니다.