링크드리스트에 대해 살펴보고 이를 이용하여 리스트를 구현해봅시다.
이전포스트 : 리스트의 이해와 배열을 통한 구현
링크드리스트(연결리스트, Linked List)
링크드리스트는 노드들로 이어진 리스트를 말합니다. 종류와 구현 방법에 따라 다르겠지만 노드는 보통 데이터를 저장하는 부분과, 다음 노드를 가르키는 부분으로 구성됩니다. 링크드리스트는 처음과 끝을 가르키는 포인터들을 이용해 리스트를 관리합니다. 끝 노드는 null값을 가지고 있습니다.
노드 구현
앞서 그림에서 보았듯이 노드에는 데이터를 저장하는 부분과 다음 노드를 가르키는 부분이 있습니다. 이전 포스트에서도 그랬듯 이번에도 쇼핑리스트를 만들어보도록 합시다.(저장하는 값이 string형 값입니다.)
// c++
#include<iostream>
#include<string>
using namespace std;
class Node {
public:
string data;
Node* next;
};링크드리스트 구현
앞서 구현한 노드클래스를 사용하여 링크드리스트에서 필요한 head와 tail을 구현합니다.
class LinkedList {
public:
Node* head;
Node* tail;
LinkedList() {
head = nullptr;
tail = nullptr;
}
};아무런 노드가 없는 리스트의 경우 head와 tail은 null을 가르킵니다.
리스트 구현
이제 리스트 클래스에서 사용될 메서드들을 구현해봅시다. 이전포스트에서와 마찬가지로 삽입, 삭제 등 4가지 함수만 사용하기로 합시다. 먼저 삽입 함수를 살펴봅시다.
add()
class List {
private:
LinkedList listADT;
public:
void add(string str) {
Node* newNode = new Node;
newNode->data = str;
newNode->next = nullptr;
if (isEmpty()) { // 리스트가 비어있는 경우
listADT.head = newNode;
listADT.tail = newNode;
}
else { // 리스트에 값이 있던 경우
listADT.tail->next = newNode;
listADT.tail = newNode;
}
};입력받은 string 값을 새로운 노드에 넣고, 이 노드를 기존 리스트에 붙이는 작업을 하는 함수입니다. 삽입된 노드는 리스트의 맨 뒤에 위치하기 때문에 다음 노드를 가르키는 분에 null값이 들어가게 됩니다. 리스트가 비어있는 경우와 기존에 값이 있던 경우 구현이 달라지기 때문에 조건문을 사용해 다르게 구현하였습니다.
리스트가 비어있는 경우에는 다음과 같은 상황이 되도록 코드를 짜주면 됩니다.
리스트에 값이 있던 경우에는 맨 끝에 있던 노드가 새로운 노드를 가르키도록 하고, tail이 새로운 노드를 가르키게 해주면 새로운 노드가 삽입됩니다.
다음으로는 삭제 함수를 구현해보도록 합시다.
del()
void del(string str) {
if (isEmpty()) { cout << "리스트가 비어있습니다."; return; }
for (Node* now = listADT.head; now != nullptr; now = now->next) {
if (now->data == str) {
if (now == listADT.head) { // 값이 맨 앞에 있는 경우
listADT.head = now->next;
delete now;
}
else {
Node* pre = listADT.head;
while (pre->next != now) pre = pre->next;
pre->next = now->next;
delete now;
}
break;
}
}
};입력받은 값이 리스트에 있는 경우 해당 노드를 삭제하는 함수입니다. 노드를 가르키는 포인터 now를 이용하여 head부터 tail까지 탐색하며 입력받은 값이 리스트에 있을 경우 삭제합니다. 해당 값이 맨 첫번째 노드에 있는 경우와 그 이외의 경우의 구현이 서로 다르기 때문에 이를 조건문으로 구분하였습니다.
먼저 값이 맨 앞에 있는 경우는 헤드를 다음 노드로 옮긴 후 지우려는 값이 있는 노드를 삭제해주면 됩니다. 그러나 그 이외의 경우에는 이전 노드의 next가 지우려는 노드의 next를 가르키도록 해야 정상적으로 리스트를 구성할 수 있습니다.
pre가 while loop을 돌면서 삭제하는 노드의 전 노드를 가르키게 되고, 이를 통해 전 노드의 next가 삭제 노드의 next와 동일 값이 되도록 설정한 후 삭제 노드를 제거합니다.
isEmpty()와 displayAll()
isEmpty()는 간단히 수현할 수 있습니다. head가 null을 갖는 경우 리스트가 비어있다고 할 수 있기 때문입니다. displayAll() 역시 이전에 작성하였던 del()에서의 노드를 탐색하는 부분을 가져와 데이터를 하나씩 출력하는 코드를 작성하면 됩니다.
bool isEmpty() {
if (listADT.head == nullptr) return true;
else return false;
};
void displayAll() {
cout << "쇼핑리스트 목록입니다.\n";
int i = 1;
for (Node* now = listADT.head; now != nullptr; now = now->next) {
cout << i << ". " << now->data << endl;
i++;
}
};
};
이로써 List 클래스 구현이 완료되었습니다.
링크드리스트를 통한 리스트ADT의 장단점
배열을 통한 리스트와 다르게 링크드리스트를 사용하면 메모리를 동적으로 사용할 수 있다는 장점이 있습니다. 따라서 main()함수에서 입력되는 값의 수를 제한할 필요가 없습니다.
int main() {
List list1;
cout << "쇼핑리스트에 넣을 항목을 입력하시오. (다음 단계로 넘어가려면 q 입력)\n";
cout << "입력할 항목 : ";
do{
string t;
cin >> t;
if (t == "q") break;
list1.add(t);
} while (true);
cout << "집에 있는 물건들을 살펴보고 삭제할 물건들은 삭제합시다.(다음 단계로 넘어가려면 q 입력)\n";
cout << "삭제할 항목 : ";
do {
string t;
cin >> t;
if (t == "q") break;
list1.del(t);
} while (true);
cout << "장 볼 리스트를 출력합니다.\n";
list1.displayAll();
}이는 배열로 구현할 때와 달리 리스트에 값을 메모리가 허용하는 한 원하는 만큼 넣을 수 있고, 리스트의 값이 적게 들어 있는 경우 사용할 수 없었던 부분의 메모리까지 사용할 수 있다는 것을 의미합니다.
다만 링크드리스트의 경우 하나의 데이터를 담는 공간이 배열과 다르게 다음 노드를 가르키는 부분까지 포함해야 하므로 메모리가 한정되어있는 상황에서는 프로그램이 제대로 동작하지 않을 가능성이 있습니다.
이 뿐만 아니라, 배열은 메모리가 연속적으로 구성되어 있어 탐색 시 index를 통해 빠른 탐색이 가능하지만, 링크드리스트의 경우 노드가 메모리에 랜덤으로 분포해 있어서 탐색 시 시간복잡도가 배열의 경우보다 안 좋아지게 됩니다.(ex. 한 노드에서 다른 노드를 필요로 하는 경우)
확장(이중 연결, 환형 등)
단순 링크드리스트에서는 한 노드에서 다른 노드를 필요로 하는 경우(삭제함수같은 경우) head부터 다시 탐색해야 이를 찾을 수 있었습니다. 이를 해결하기 위해 Doubly linked list와 circular linked list가 등장하게 되었습니다.
Doubly linked list(이중 - )
이중 링크드리스트의 노드는 다음 노드를 가르키는 포인터 뿐만 아니라 이전 노드를 가르키는 포인터 또한 갖게 됩니다. 이로써 우리는 특정 데이터 이후의 노드 탐색 뿐만 아니라 이전의 노드들도 쉽게 접근할 수 있게 됩니다.
사진 출처(외부링크) : 이중링크드리스트 - 구현부를 살펴볼 수 있습니다.
Circular linked list(환형 - , 원형 - )
환형 링크드리스트는 끝 노드가 처음 노드를 가르키도록 한 링크드리스트입니다. 따라서 하나의 노드에서 모든 노드로의 접근이 가능합니다.
사진 출처(외부링크) : 환형링크드리스트 - 구현부를 살펴볼 수 있습니다.
