본문으로 건너뛰기

연결 리스트 (Linked List)

개요​

배열의 한계, 노드 기반 연결 리스트 구조, 단일·이중 연결 리스트 표현.

Array의 특징과 한계​

자료를 순차적으로 저장하는 가장 간단한 방법은 Array를 사용하는 것이다. Array는 index(첨자)를 통해 원하는 원소에 직접 접근하는 random access(임의참조)가 가능하다는 장점이 있다.

하지만 다음과 같은 명확한 단점도 존재한다.

  • 고정된 크기: Array는 컴파일 시점에 크기가 결정되어, 프로그램 실행 중에는 크기를 변경할 수 없다.
  • 삽입의 어려움: 맨 앞이나 중간에 새로운 자료를 삽입하면, 그 위치 이후의 모든 원소를 뒤로 한 칸씩 이동시켜야 하는 부담이 있다.
  • 삭제의 어려움: 중간의 원소를 삭제하면, 삭제된 공간을 메우기 위해 뒤따르는 모든 원소를 앞으로 한 칸씩 이동시켜야 한다.

Linked List의 개념​

Linked List는 Array와 함께 순차적 자료를 표현하는 데 적합한 자료구조이다. 이는 각 원소가 다음 원소를 가리키는 방식으로 연결된 구조를 가진다.

  • node(노드): Linked List의 각 원소를 의미하며, Array의 원소에 해당한다.
  • data(자료): node에 저장되는 실제 값이다.
  • link(링크): 다음 node를 가리키는 포인터(주소)이다.

head('front') 포인터가 첫 번째 node를 가리키고, 각 node의 link가 순차적으로 다음 node를 가리키며, 마지막 node의 link는 아무것도 가리키지 않는 상태(NULL)가 된다.

Linked List의 구현​

자기참조 구조체​

Linked List의 node를 구현하기 위해서는 self reference struct(자기참조 구조체)를 사용한다. 이는 구조체의 멤버 중 하나로 자기 자신을 가리키는 포인터 변수를 가지는 구조체를 말한다.

struct selfref {
    int n; // data 부분
    struct selfref *next; // link 부분. 자기 자신을 가리키는 포인터.
};

구조체는 자기 자신의 포인터를 멤버로 가질 수는 있지만, 자기 자신을 멤버로 포함할 수는 없다. 이는 무한한 크기를 정의하게 되어 컴파일 오류를 발생시킨다.

간단한 Linked List 생성​

  1. malloc() 함수를 사용하여 node를 저장할 공간을 동적으로 할당한다.
  2. 각 node의 data 멤버에 값을 저장하고, link 멤버(next)는 초기 상태로 NULL을 저장한다.
  3. 첫 번째 node의 link 멤버에 두 번째 node의 주소값을 저장하여 두 node를 연결한다.

C

// ... 구조체 정의 이후 ...
list *first, *second;
first = (list *)malloc(sizeof(list));
second = (list *)malloc(sizeof(list));

first->n = 100;
first->next = NULL;

second->n = 200;
second->next = NULL;

// 첫 번째 노드가 두 번째 노드를 가리키도록 연결
first->next = second;

주요 연산​

Node Traversal(노드 순회)​

Node Traversal은 Linked List의 모든 node를 순서대로 참조하는 방법이다. head 포인터에서 시작하여 각 node의 link를 따라가다 link가 NULL인 마지막 node에 도달하면 순회가 종료된다.

Node 추가​

새로운 node를 생성하여 Linked List의 마지막에 추가하는 과정은 다음과 같다.

  1. createNode()와 같은 함수를 사용하여 추가할 새 node를 생성한다. 이 node의 data를 채우고 link는 NULL로 초기화한다.
  2. Node Traversal을 통해 리스트의 마지막 node까지 이동한다.
  3. 마지막 node의 link가 새로 생성한 node를 가리키도록 주소값을 저장한다.

코드 예시​

다음은 Linked List를 다루는 주요 함수의 개념적 구현이다.

  • createNode(char \*name): 문자열을 data로 갖는 새로운 NODE를 생성하고 그 주소를 반환한다.
  • append(LINK head, LINK cur): cur 포인터가 가리키는 NODE를 head가 시작인 Linked List의 마지막에 추가한다.
    • 만약 head가 NULL이면 (리스트가 비어있으면), cur가 새로운 head가 된다.
    • 그렇지 않으면, 리스트의 끝까지 순회하여 마지막 NODE의 next에 cur를 연결한다.
  • printList(LINK head): head부터 시작하는 Linked List를 Node Traversal하며 각 NODE의 data를 출력한다.

Linked List의 장단점​

장점​

  • 동적 크기 조절: 프로그램 실행 중에 필요에 따라 node를 동적으로 생성하고 추가할 수 있어 메모리를 효율적으로 사용 가능하다.
  • 효율적인 삽입/삭제: 중간에 node를 삽입하거나 삭제할 때, 주변 node의 link 값만 변경하면 되므로 Array에 비해 재배치 과정이 빠르고 간단하다.

단점​

  • 느린 random access: 특정 위치의 node에 접근하려면 head부터 시작하여 link를 순차적으로 따라가야 하므로, Array처럼 특정 index로 한 번에 접근할 수 없다. 이로 인해 검색 속도가 느리다.