Chapter 03. 연결 리스트 (Linked List)

연결 리스트 (Linked List)

노드들이 선형적으로 순서화된 형태의 집합체

 

노드(Node) : [원소 , 주소] 와 같이 원소값과 다음 노드 주소를 저장하는 단위구조 

• 데이터 : 저장할 원소의 형태에 따라 하나 이상의 필드로 구성
• 링크 : 메모리 참조 변수를 사용하여 주소에 대한 참조값 저장

 

 

단일 연결 리스트 (Singly Linked List)

: 노드 하나가 링크 필드에 의해서 다음 노드와 연결되는 구조를 가진 연결 리스트

head : 처음 노드

tail : 마지막 노드

null을 참조하는 next값을 가지는 노드가 tail

 

• 장점 : 고정된 크기를 갖지 않으며, 노드를 추가하거나 삭제함으로써 사이즈를 조정 가능
• 단점 : 배열과 달리 원하는 element에 접근하기 위해 순차적으로 접근해야함

 

 

추가 Append(element)

 

삭제 Delete(index)

 

삽입 Insert(index, element)

 

 

이중 연결 리스트 (Doubly Linked List)

단일 연결 리스트의 탐색기능을 개선한 양방향 탐색이 가능한 자료구조

다음 노드 뿐만 아니라 이전 노드를 가리키는 포인터를 가짐

 

 

삽입

 

삭제

 

 

환형 연결 리스트

단일 연결 리스트의 tail과 head가 next 포인터를 이용하여 연결되어 있는 형태

Cursor라고 불리우는 노드를 갖고 있어서, 환형 연결 리스트를 탐색할 때에 시작할 지점을 정해줌

 

 

연결 리스트를 이용한 기본 연산

• Empty 
• List_size
• Append
• Add_Front
• Insert
• Delete
• Print

 

 

코드

#include <iostream>
#include <string>
using namespace std;

class Node {
    int elem;
    Node* next;

    friend class S_LinkedList;
};

class S_LinkedList {
public:
    S_LinkedList();
    int List_size();
    bool Empty();
    void Print();
    void Append(int elem);
    int Delete(int idx);
    void Insert(int idx, int elem);

private:
    Node* head;
    Node* tail;
};

S_LinkedList::S_LinkedList() {
    head = new Node;
    tail = new Node;

    head = NULL;
    tail = NULL;
}

bool S_LinkedList::Empty() {
    return (head == NULL && tail == NULL);
}

int S_LinkedList::List_size() {
    int list_size = 0;
    if (Empty()) {
        return list_size;
    }

    else {
        Node* cur_node = head;
        while(cur_node->next != NULL) {
            list_size++;
            cur_node = cur_node->next;
        }
        list_size++;
        return list_size;
    }
}

void S_LinkedList::Print() {
    if(Empty()) {
        cout << "empty" << endl;
    }
    else {
        Node* cur_node = head;
        while (cur_node->next != NULL) {
            cout << cur_node->elem << ' ';
            cur_node = cur_node->next;
        }
        cout << cur_node->elem << endl;
    }
}

void S_LinkedList::Append(int elem) {
    Node* new_node = new Node;
    new_node->elem = elem;
    new_node->next = NULL;

    if (Empty()) {
        head = new_node;
        tail = new_node;
    }
    else {
        tail->next = new_node;
        tail = tail->next;
    }
}

int S_LinkedList::Delete(int idx) {
    int removeNum = 0;
    int cnt = 0;
    Node* cur_node;
    Node* pre_node;

    if (Empty() || List_size() <= idx) {
        return -1;
    }

    else if (idx == 0) {
        if (List_size() == 1) {
            removeNum = head->elem;
            tail = NULL;
            head = NULL;
        }
        else {
            cur_node = head;
            removeNum = cur_node->elem;
            head = cur_node->next;
        }
    }

    else {
        pre_node = cur_node = head;
        while(cnt != idx) {
            pre_node = cur_node;
            cur_node = cur_node->next;
            cnt++;
        }

        removeNum = cur_node->elem;
        pre_node->next = cur_node->next;

        if (cur_node == tail) {
        tail = pre_node;
        }
    }

    return removeNum;
}

void S_LinkedList::Insert(int idx, int elem) {
    Node* new_node = new Node;
    new_node->elem = elem;

    Node* pre_node;
    Node* cur_node;
    int cur_idx = 0;

    if (idx == 0) {
        if (Empty()) {
            head = new_node;
            tail = new_node;
        }
        else {
            new_node->next = head;
            head = new_node;
        }
    }
    else if (idx < 0 || idx > List_size()) {
        cout << "Index Error" << endl;
    }
    else if (idx == List_size()) {
        Append(elem);
    }
    else {
        pre_node = cur_node = head;
        while(cur_idx != idx) {
            pre_node = cur_node;
            cur_node = cur_node->next;
            cur_idx++;
        }
        pre_node->next = new_node;
        new_node->next = cur_node;
    }
}