링크드리스트(Linked List)

링크드리스트(Linked List)

배열의 한계

소프트웨어는 종종 프로그래머에게 배열 이상의 그 무엇을 요구할 때가 있습니다. 만약 임의의 디렉토리 내에 존재하는 파일의 목록을 소프트웨어가 필요로 한다면 어떻게 해야할까요? 그 디렉토리에는 파일이 전혀 없을 수도 있고, 10개도 안되는 파일만 존재할 수도 있습니다. 하지만 운이 나쁘면 수천, 수만 개의 파일이 있을 수도 있습니다. 분명한 사실 한 가지는 디렉토리 내에 존재하는 파일의 수는 프로그래머의 염원과는 상관없이 정해진다는 것입니다.
'파일이 항상 10개 미만으로만 있으면 좋겠다.' 라는 염원 하나로 다음과 같이 배열을 선언하겠습니까?

char* files[10];

그렇다고 다음과 같이 무작정 큰 배열을 선언할 수도 없는 일입니다. 게다가 문제를 완전히 해결하지도 못합니다. 65535개보다 더 많은 파일이 존재할 수도 있으니 말입니다.

char* files[65535];

너무 작게 선언하면 계획된 일을 처리할 수 없고 무작정 크게 선언하면 메모리가 울 것 같습니다. 이 문제를 해결하기 위해 필요한 것은 배열처럼 데이터 집합을 보관하는 기능을 가지면서도 한편으로는 배열과는 달리 유연하게 크기를 바꿀 수 있는 자료구조입니다. 이 자료구조는 '리스트(List; 목록)'라고 불립니다.
리스트는 스택과 큐, 그리고 트리와 같은 자료구조를 이해할 수 있는 기반이 된다는 점에서 중요한 의미를 가집니다. 또한 리스트 그 자체 뿐 아니라 자료구조를 다루기 위해 필요한 메모리 처리 기법에 익숙해지는 기회가 될 것입니다.

링크드 리스트(Linked List)

링크드 리스트(Linked List)는 리스트를 구현하는 여러가지 기법 중에서도 가장 간단한 방법으로 꼽히는 자료구조 입니다. 자료구조를 처음 접하는 사람들에겐 아주 좋은 공부거리라고도 할 수 있습니다.

먼저, 리스트 내의 각 요소는 노드(Node)라고 부릅니다. 노드는 '마디'라는 뜻인데, 링크드 리스트는 '노드를 연결해서 만드는 리스트'라고 하여 붙여진 이름입니다. 참고로 '노드'는 스택, 큐, 트리 등에서 계속해서 사용될 용어입니다. 링크드 리스트의 노드는 다음과 같이 데이터를 보관하는 필드와 다음 노트와으이 연결고리 역할을 하는 포인터로 이루어집니다.

데이터와 포인터로 이루어진 노드들을 다음 그림처럼 엮으면 링크드 리스트가 되는 것입니다.

리스트는 기다랗게 생긴 것이 지네와 비슷한데, 지네처럼 리스트 또한 헤드(Head; 머리)와 테일(Tail; 꼬리)을 가지고 있습니다. 리스트의 첫 번째 노드를 헤드라고 하고 마지막 노드를 테일이라고 합니다.

이는 다루어야 하는 데이터 집합의 크기를 미리 알지 못한다 하더라도 걱정할 필요 없는 방법이기 때문에 좋은 아이디어라고 볼 수 있습니다. 데이터가 늘어날 때마다 노드를 만들어 테일에 붙이면 되기 때문입니다. 이렇게 붙인 노드는 새로운 테일이 되고 이전에 테일이었던 노드는 평범한 노드가 됩니다. 리스트 사이에 새로운 노드를 끼워 넣거나 제거하는 것도 아주 쉽습니다. 해당 노드를 가리키는 포인터만 교환해주면 되기 때문입니다. 그럼, 링크드 리스트의 구현에 대해 이야기 하면 다음과 같습니다.

C언어로 표현하는 링크드 리스트의 노드

링크드 리스트의 기본 연산을 시작하기 전에, 노드를 어떻게 표현해야 할 지를 알아두어야 합니다. 링크드 리스트의 노드는 C언어로 표현하면 다음과 같은 구조체로 나타낼 수 있습니다.

struct Node
{
    int Data; /* 데이터 필드 */
    struct Node* NextNode; /* 다음 노드를 가리키는 포인터 */
};

이 코드에서는 Data 필드의 자료형이 int 이지만 이는 어디까지나 예제를 단순하게 하기 위한 것이기 때문에 이후, 링크드 리스트를 활용한 프로그램을 작성할 때에는 상황에 맞게 바꾸어 사용하면 됩니다. 한편, 이렇게 정의된 Node 구조체의 인스턴스를 만들려면 항상 귀찮은 struct 키워드를 동반해야 합니다. 다음과 같이 말입니다.

struct Node MyNode;

따라서 다음과 같이 typedef 키워드를 이용하여 Node 구조체를 정의하여 사용할 것입니다.

typedef struct tagNode
{
    int Data; /* 데이터 필드 */
    struct tagNode* NextNode; /* 다음 노드를 가리키는 포인터 */
} Node;

이렇게 선언한 Node 구조체는 다음과 같이 간편하게 인스턴스를 만들 수 있습니다. struct 키워드 없이 말입니다.

Node MyNode;

링크드 리스트의 주요 연산

기본적으로 링크드 리스트를 구축하고 링크드 리스트에 있는 자료를 사용하기 위해 필요한 연산은 다음 다섯가지입니다.

1. 노드 생성/소멸
2. 노드 추가
3. 노드 탐색
4. 노드 삭제
5. 노드 삽입

노드의 생성/소멸, 추가, 삭제, 삽입은 링크드 리스트의 자료구조를 구축하기 위한 연산이고 리스트 탐색은 구축되어 있는 링크드 리스트의 데이터를 활용하기 위한 연산입니다.
백조가 우아하게 호수 위에 떠다니는 이면에는 물 위에 떠 있기 위한 백조의 발버둥이 있는 것 처럼, 링크드 리스트가 단순한 자료구조를 유지하기 위해서는 위의 다섯 가지 연산을 지원하기 위해 자유저장소(Free Store)와 포인터를 완벽하게 이해해야 합니다.

링크드 리스트의 장/단점

장점

새로운 노드의 추가/삽입/삭제가 쉽고 빠릅니다. 배열은 요소를 삽입하거나 제거하기가 어렵습니다. 그리고 현재 노드의 다음 노드를 얻어오는 연산에 대해서는 비용이 발생하기 않습니다. (이는 장점이라고 하기는 어렵지만 단점은 아니기 때문에 장점으로 분류했습니다.)

단점

다음 노드를 가리키려는 포인터 때문에 각 노드마다 4byte의 메모리가 추가로 필요합니다. 그리고 특정 위치에 있는 노드를 얻는데 드는 비용이 크며 속도도 느립니다. 노드의 개수가 n이라면 최악의 경우 n회의 노드 탐색 루프를 실행해야 특정 위치에 있는 노드를 찾을 수 있습니다. 반면 배열은 상수 시간에 노드를 얻을 수 있습니다.