4-2. 연결 리스트란?

연결 리스트란?

프로그래밍을 할 때 배열은 아주 많이 사용된다.

해당 블로그에서는 앞서 배열을 이용해 스택과 큐를 구현하는 방법을 소개했다.

그런데 배열을 이용할 때는 항상 따라오는 단점이 하나 있다. 바로 고정된 크기이다.

이것을 해결하기 위해 사용하는 방법이 연결 리스트(linked list)이다. 연결 리스트는 크기를 늘리고 줄이고 할 수 있다.

📍 후에 리스트를 다룰 때 다시 얘기하겠지만 연결 리스트와 리스트는 다르다.

 

연결 리스트를 쉽게 이해하기 위해 두 가지 사진을 가져왔다.

왼쪽 사진은 2호선 지하철, 오른쪽 사진은 화물 기차의 사진이다.

2호선은 8-4칸까지 있기 때문에 처음 만든 크기대로 계속 사용될 것이다.

 

반면 오른쪽 사진의 화물 기차는 뒤에 컨테이너를 붙였다 뗐다 하면서 연결할 개수를 조절할 수 있다.

이것이 연결 리스트의 개념과 동일하다.

 

프로그래밍 언어로 연결 리스트를 구현할 때는 앞서 알아봤던 자기 참조 구조체의 포인터로 노드들을 연결한다.

typedef struct _node{
    string name;
    struct _node *next; // 자기 참조
} Node;

자기 참조 포인터로 다음 노드를 연결한다. 원하는 개수만큼 연결하면 되므로 크기는 제한이 없다.

연결 리스트의 특징을 알아보자.

• 크기가 고정되지 않는다. 메모리를 할당할 수 있는 한 계속 크기를 늘릴 수 있다.
• 중간 위치에 자료를 삽입할 수 있다. (배열도 가능하지만 번거로움)
• 중간 위치의 데이터를 삭제하는 것이 배열보다 수월하다.
• 배열에 비해  상대적으로 구현이 어렵고 오류가 나기 쉽다.

---

연결 리스트의 구조

위 그림에서 파란색 박스를 노드(node)라고 부른다.

연결 리스트는 노드들의 집합이며 노드에는 데이터가 저장되고 다른 노드와 연결하는 부분이 있다.

데이터를 저장하는 부분을 데이터 필드(data field), 다른 노드와 연결하는 부분을 링크 필드(link field)라고 한다.

 

연결 리스트는 첫 번째 노드를 알면 링크 필드로 연결된 모든 노드에 접근할 수 있다.

그래서 연결 리스트에는 첫 번째 노드를 가리키는 포인터가 필요하고 이것을 헤드 포인터(head pointer)라고 한다.

더 이상 연결할 노드가 없는 마지막 노드의 링크 필드는 NULL로 설정한다.

---

연결 리스트의 종류

• 단순 연결 리스트(singly linked list)
  
  • 하나의 방향으로만 연결되어 있으며, 마지막 노드의 링크 필드는 NULL값을 갖는다.

• 원형 연결 리스트(circular linked list)
  • 마지막 노드의 링크 필드가 NULL값을 갖는 것이 아닌 첫 번째 노드를 다시 가리킨다.

• 이중 연결 리스트(doubly linked list)
  
  • 각 노드마다 링크 필드가 2개씩 존재하고 링크 필드는 각각 선행 노드와 후행 노드를 가리킨다.