[c++] 알고리즘 개념공부 :: 자료구조 - 연결 리스트

연결 리스트

1. 리스트란?
2. 정의
3. 배열과의 비교
4. 연산
   1. 삽입
   2. 삭제
   3. 접근
5. 종류 / 구현

 

리스트란?

리스트는 순서를 가진 항목들의 모임이다. 이를 나타내는 대표적인 방법은 2가지가 있는데, 하나는 배열을 이용하는 방법이고 나머지 하나는 연결리스트를 이용하는 방법이다. 배열을 이용한 리스트를 선형리스트라고 하는데 구현 자체는 간단하고 임의접근이 가능하지만, 삽입 / 삭제 연산 시 다른 요소들의 이동이 불가피하므로 오버헤드가 크다. 연결리스트는 구현이 복잡하고 순차접근이 필요하지만 삽입, 삭제가 효율적이다.

 

정의

연결리스트란 아래의 그림과 같이 데이터와 링크로 이루어진 노드로 구성되어있다. 링크는 다음 요소를 가리키는 포인터이다. 연결리스트의 처음에는 헤드 포인터가 헤드 노드를 가리키고 있으며, 마지막 노드의 링크는 NULL값이다.

요소를 추가할 때마다 노드가 하나씩 늘어나며, 각 노드들은 링크로 연결되어있다. 따라서 노드들은 계속해서 생겨날 수 있으며 컴파일시간에 결정되는 요소가 아니기 때문에, 이는 메모리 동적할당으로 구현된다.

 

배열과의 비교

• 순차접근이 필요하다.
• 메모리 상에서 인접해있을 필요가 없다.
• 메모리 크기 제한이 없다시피하다.
• 삽입 / 삭제가 효율적이다.

 

연산

삽입

위와 같은 상태에서 노드4를 삽입하고 싶을 때는, 노드 1의 link가 노드4를 가리키게 하고 노드4의 link가 노드2를가리키게 세팅하기만 하면 된다.

배열에서 삽입과정은 한 요소를 특정 위치에 삽입하기 위해, 해당 index 이후의 요소들을 모두 이동시켜야했지만 연결 리스트는 그럴 필요가 없다. 하지만 삽입 위치의 전후 노드를 찾기 위해 순차접근을 해야하는 불편함은 있을 것이다.

 

삭제

위와 같은 상태에서 노드 2를 삭제하고 싶을 때는 노드1의 링크가 노드3을 가리키게 하면 된다.

이렇게 삭제할 노드2는 heap 메모리 영역에서 메모리를 해제해주어야 한다.

 

접근

접근은 위에서 배열과 비교했듯이 순차접근이 필요해서 성능이 좋지 않다. 이를 보안하기 위해 해시 값으로 이어진 또다른 링크를 만들어두기도 한다.

 

종류 / 구현

• 단순 연결 리스트

#include <iostream>
#include <string>

using namespace std;

struct Node {
    int data;
    Node* link = nullptr;
};

void printNodes(Node* head) {
    while (head != nullptr) {
        cout << (*head).data << endl;
        head = head->link;
    }
}
void push(Node* node, Node*& head) {
    node->link = head;
    head = node;
}

Node* pop(Node*& head) {
    if (head == nullptr)
        return nullptr;
    Node* tmp = head;
    head = (*head).link;
    return tmp;
}

int main() {
    Node n1; Node n2; Node n3;
    n1.data = 1; n2.data = 2; n3.data = 3;

    Node* head = nullptr; 

    push(&n3, head);
    push(&n2, head);
    push(&n1, head);
    printNodes(head); // 삽입 후 출력
    cout << endl;

    Node* n4 = pop(head); 
    if (n4 != nullptr) {
        cout << "삭제된 데이터 : " <<n4->data << endl; // 삭제한 데이터 출력
    }
    printNodes(head); // 삭제 후 출력
}

• 원형 연결 리스트

#include <iostream>
#include <string>

using namespace std;

struct Node {
    int data;
    Node* post_link = nullptr;
    Node* pre_link = nullptr;
};

void printNodes(Node* head) {
    while (head != nullptr) {
        cout << (*head).data << endl;
        head = head->pre_link;
    }
}
void push(Node* node, Node*& head) {
    node->pre_link = head;
    head = node;
}

Node* pop(Node*& head) {
    if (head == nullptr)
        return nullptr;
    Node* tmp = head;
    head = (*head).link;
    return tmp;
}

int main() {
    Node n1; Node n2; Node n3;
    n1.data = 1; n2.data = 2; n3.data = 3;

    Node* head = nullptr; 

    push(&n3, head);
    push(&n2, head);
    push(&n1, head);
    printNodes(head); // 삽입 후 출력
    cout << endl;

    Node* n4 = pop(head); 
    if (n4 != nullptr) {
        cout << "삭제된 데이터 : " <<n4->data << endl; // 삭제한 데이터 출력
    }
    printNodes(head); // 삭제 후 출력

}

• 이중 연결 리스트