03. 자료구조론 - Linked List

List 

리스트는 여러 요소들의 순서가 있는 sequence 입니다. 

리스트에서는 요소를 delete, find, insert 하는 등의 operation을 수행할 수 있어야하고, 이러한 리스트를 구현하는 방법에는 두가지가 있습니다.

1. 배열로 List 구현

첫번째로 array를 이용하여 리스트를 구현할 수 있습니다. 

배열로 구현한 리스트에서 insert를 수행하려면 위와 같이 X가 들어가려는 위치의 뒤쪽 요소들을 모두 뒤로 한 칸 씩 민 후, 빈 자리에 X를 넣어주어야합니다. 동일하게 delete를 수행할 때에도, X를 제거한 후 뒤쪽 요소들을 한 칸 씩 앞으로 당겨주어야 합니다.

따라서 이러한 배열로 만든 리스트는 리스트의 중간에 insert나 delete를 수행하기 어렵다는 단점이 있습니다. 이 단점은 리스트의 앞쪽에서 해당 동작이 수행될수록 두드러집니다. 

맨 앞에서 해당 동작을 수행할 경우, 첫번째 요소를 빼고 모든 요소를 옮겨야하므로 최악의 시간복잡도는 O(N)이 됩니다.

그리고 평균적인 시간복잡도는 절반의 요소를 옮기는 것이므로 불필요한 계수를 제거하면 동일하게 O(N)이 됩니다.

 

2. LInked list로 List 구현

링크드리스트는 말그대로 리스트 내의 요소요소가 연결되어있는 리스트입니다. 그 요소는 해당 요소의 값을 담고있는 element와 리스트의 다음 요소를 가리키는 pointer로 이루어진 구조체로 되어있습니다.

따라서 링크드리스트는 해당 구조체들이 포인터를 통해 이어진 형태를 하고 있으며, 다음에 나올 요소가 포인터를 통해 지정되기 때문에 연결된 요소들이 메모리 상에서 인접해있지 않아도 됩니다.

그리고 마지막 요소의 포인터는 NULL을 가리키고 있게 됩니다.

그림의 윗부분과 같이 리스트가 이어져있을 때, 포인터는 다음 노드의 주소를 담고 있습니다.

그리고 그림의 아랫부분과 같이 주소 순으로 노드들을 정렬하면, 리스트 상에서 인접한 노드들이 메모리 상에서는 인접해있지 않을 수 있다는 것을 알 수 있습니다.

링크드리스트의 한 노드를 이루는 구조체는 다음과 같이 만들 수 있습니다.

typedef struct _Node {
    int element; // 노드의 값
    Node* next; // 다음 노드의 주소를 가리키는 포인터
} Node;

 

1. Insert

링크드리스트에서 특정 위치 P 뒤에 새로운 값 K를 insert하는 것은 다음과 같이 이루어집니다.

1) X 노드의 포인터가 기존 P의 포인터가 가리키던 노드를 가리키도록 변경

2) P 노드의 포인터가 X를 가리키도록 변경

void Insert(List list, int x, Node* p) {
    Node* newNode = (Node*) malloc(sizeof(Node));
    newNode->element = x;
    newNode->next = p->next; // 위 1번 과정
    p->next = newNode; // 위 2번 과정
}

2. Delete

특정 위치 P의 노드를 리스트에서 delete하는 것은 다음과 같이 이루어집니다.

1) P 노드를 가리키던 P의 앞 노드의 포인터가 P가 가리키고 있는 P의 다음 노드를 가리키도록 변경

2) P의 포인터가 NULL을 가리키도록 변경

 

// x를 element로 갖는 노드의 이전 노드를 구하는 함수
Node* FindPrevious(List list, int x) {
    Node* p = list;
    while (p->next != NULL && p->next->element != x) {
    	p = p->next;
    }
    return p
}

void Delete(List list, int x) {
    Node *p, *tmp;
    p = FindPrevious(list, x);
    if (p->next != NULL) {
        tmp = p->next; // p가 지울 노드의 이전 노드를 찾은 것이므로, tmp는 삭제할 노드가 됨.
        p->next = tmp->next; // tmp는 삭제될 것이므로, 이제 tmp의 다음노드는 tmp의 이전노드가 가리키도록 함
        free(tmp);
    }
}

3. 리스트 생성

새로운 링크드리스트를 생성하려면 리스트의 첫 노드를 가리킬 헤더노드를 하나 생성해주면 됩니다. 헤더노드의 값은 의미가 없고 헤더노드의 포인터만 알고있으면 리스트에 접근할 수 있게됩니다.

typedef Node* List;

List MakeList() {
    List list = (List) malloc(sizeof(Node));
    list->next = NULL;
    return list;
}

4. IsEmpty

리스트가 비어있는지는 헤더노드에 다음 노드를 가리키는 포인터가 존재하는지를 판단하여 알 수 있습니다. 

boolean IsEmpty(List list) {
	return list->next == NULL;
}

5. Find

링크드리스트에서 특정 값을 element로 갖는 노드를 찾는 방법은 헤더부터 시작하여 노드의 포인터를 차례차례 따라가면서 모든 노드를 찾아보면 됩니다. 

리스트의 마지막노드의 포인터는 NULL을 가리키므로, p가 NULL이 되면 찾는 값이 리스트에 없는 것입니다.

Node* Find(int x, List list) {
    Node* p;
    p = list->next; // 헤더의 포인터가 가리키는 노드 = 리스트의 첫번째 노드를 p가 가리키게 됨
    while (p != NULL && p->element != x) {
    	p = p->next;
    }
    return p;
}

링크드리스트는 특정 노드를 delete하거나 특정 노드 다음 위치에 새로운 노드를 insert 하는 경우 노드들의 링크만 새로 연결해주면 되므로 시간복잡도가 O(1) 만큼걸리게 되어 배열을 이용한 리스트보다 더 낫다.

하지만 링크드리스트는 중간에 있는 노드에 바로 접근할 수 없고, 헤더부터 시작하여 링크를 하나하나 따라가서 접근할 수 밖에 없기 때문에 특정 노드에 접근하는데 O(N) 만큼의 시간이 필요하다는 단점이 있다.

이중 링크드리스트 (Doubly Linked List)

일반적인 링크드리스트는 다음노드를 가리키는 포인터만 가지고 있어 단방향으로 연결되어 있습니다. 따라서 어떤 노드의 앞에 있는 노드들에는 접근할 수 없습니다.

이중링크드리스트는 노드의 이전 노드를 가리키는 포인터도 갖고 있어 양방향으로 연결된 링크드 리스트입니다. 따라서 어떤 노드를 가지고 있든 다른 모든 노드에 접근할 수 있게됩니다.

따라서 기존 링크드 리스트에서는 어떤 노드의 앞 노드를 찾고자 한다면 위 Delete함수 구현에서 사용했던 FindPrevious 처럼 맨 앞에서부터 하나하나 찾아야하지만, 이중링크드리스트에서는 포인터를 따라 바로 얻을 수 있습니다.

1. Insert

이중 링크드리스트에서 insert는 단방향 링크드리스트의 insert와 비슷하게 구현되며 앞뒤포인터를 모두다 변경해주면 됩니다.

코드에 주석으로 단 1, 2, 3, 4 번은 각각 그림에서 초록색 1, 2, 3, 4에 대한 연결을 나타냅니다.

// p 노드 뒤에 element를 x로 갖는 새로운 노드를 insert 하는 함수
void Insert(List list, int x, Node* p) {
    Node* newNode = (Node*) malloc(sizeof(Node));
    newNode->element = x;
    newNode->next = p->next; // 1) 새로운 노드의 다음노드 = 기존 p의 다음노드
    newNode->next->prev = newNode; // 2) 새로운 노드의 다음노드의 이전노드 = 새로운 노드
    p->next = newNode; // 3) p의 다음노드 = 새로운 노드
    newNode->prev = p; // 4) 새로운 노드의 이전노드 = p
}

2. Delete

이중링크드리스트에서 노드 P의 삭제는 다음과 같이 이루어집니다.

1) P의 이전노드의 next가 p의 next를 가리키도록 한다.

2) P의 다음노드의 prev가 p의 prev를 가리키도록 한다.

3) P는 메모리에서 할당 해제한다.

void Delete(List list, int x) {
    Node* p = Find(list, x);

    p->prev->next = p->next;
    p->next->prev = p->prev;
    free(p);
}