연결 리스트(Linked List) 총정리

연결 리스트(Linked List), 데이터를 저장하고 연결하는 특별한 방법입니다. 연결 리스트는 ‘연결된 목록’이라는 뜻으로, 데이터를 순서대로 연결하면서 관리합니다. 이름만 들으면 어렵게 느껴질 수 있지만, 비유를 통해 쉽게 이해할 수 있습니다.

개념 설명: 비유 

연결 리스트를 손을 잡고 줄을 서 있는 친구들로 비유해 봅시다.

• 각 친구는 노드(Node)입니다. (노드 개념 모르면 노드를 클릭해서 읽어보고 오세요.)
• 친구들이 손을 잡고 있는 것은 연결 리스트에서 포인터(Pointer) 역할을 합니다.
• 손을 잡으려면 기억해야 할 것이 더 많아지고, 손을 놓지 않고는 다른 친구에게 접근하기 어렵습니다.

연결 리스트의 특징

1. 순서대로 연결됩니다
   각 노드는 다음 노드의 위치를 기억하며, 이를 통해 데이터를 순서대로 연결합니다. 더 자세한 내용은 아래에서 설명해드리겠습니다.

2. 크기가 자유롭습니다
   배열은 처음부터 크기를 정해야 하지만, 연결 리스트는 데이터가 추가될 때마다 필요한 만큼 늘어나거나 줄어들 수 있습니다.

3. 중간에 데이터를 쉽게 추가하거나 삭제할 수 있습니다
   친구들 사이에 새 친구를 넣거나 기존 친구를 빼려면, 주변 친구들의 손만 연결해 주면 됩니다.

4. 추가적인 기억 공간이 필요합니다
   배열은 데이터만 저장하지만, 연결 리스트는 데이터와 함께 다음 노드의 위치를 저장하는 포인터가 필요합니다. 따라서 더 많은 공간이 필요합니다.

5. 접근 속도가 느립니다
   배열은 바로 특정 위치로 이동할 수 있지만, 연결 리스트는 첫 번째 노드부터 순서대로 따라가야 원하는 데이터를 찾을 수 있습니다. 데이터가 많을수록 시간이 더 걸립니다.

연결 리스트와 배열의 비교

순서대로 연결?

연결 리스트가 순서대로 연결된다는 표현은 정확한 의미에서 약간 보완이 필요합니다. 연결 리스트는 노드(Node)가 서로 연결되어 있지만, 연결되는 순서는 개발자가 정의한 방식에 따라 달라질 수 있습니다. 기본적으로 연결 리스트에서는 각 노드가 다음 노드의 주소를 가리키며, 이를 통해 데이터를 특정 순서대로 탐색할 수 있게 됩니다.

정확한 연결 방식

1. 단일 연결 리스트(Singly Linked List)
   각 노드는 자신의 데이터와 다음 노드의 주소(포인터)를 저장합니다. 탐색은 앞에서부터 뒤로만 가능합니다.
   예: A → B → C → D (순서대로 연결된 것처럼 보이지만, A가 B를 가리키도록 프로그래밍한 결과입니다.)

2. 이중 연결 리스트(Doubly Linked List)
   각 노드는 앞 노드와 뒤 노드의 주소를 모두 저장합니다. 탐색이 양방향으로 가능합니다.
   예: A ↔ B ↔ C ↔ D (양쪽으로 이동 가능)

3. 원형 연결 리스트(Circular Linked List)
   마지막 노드가 첫 번째 노드를 가리키며 순환 구조를 형성합니다.
   예: A → B → C → D → A (끝없이 순환)

중요한 점

• 연결 리스트에서 “순서”는 물리적으로 데이터를 배열처럼 배치하는 것이 아닙니다.
• 노드가 포인터를 통해 서로 가리키는 방식으로 연결되기 때문에 논리적 순서를 가지는 것입니다.
• 따라서, 개발자가 노드를 어떤 순서로 연결하느냐에 따라 데이터의 흐름(순서)이 결정됩니다.

정리하자면, 연결 리스트는 물리적으로 데이터가 순서대로 저장되지는 않지만, 각 노드가 다음 노드를 가리키는 포인터를 통해 특정 논리적 순서를 가지게 됩니다. 그래서 연결 리스트를 탐색할 때는 “순서대로 연결되어 있다”고 표현할 수 있습니다.

결론

연결 리스트는 데이터를 유연하게 저장하고 관리할 수 있는 방법으로, 크기가 고정되지 않아 데이터를 자주 추가하거나 삭제해야 할 때 유리합니다. 그러나 포인터 때문에 추가적인 기억 공간이 필요하며, 데이터를 찾는 속도는 배열보다 느린 단점이 있습니다. 데이터를 저장하는 방식에 따라 연결 리스트와 배열 중 적합한 방법을 선택하는 것이 중요합니다.