Linked list (링크드 리스트, 연결리스트)

1. Linked list 란 ?

 

- 선형 데이터 구조로, 각 원소들은 연속적인 메모리에 존재하지 않으며 ( 즉, linked list의 원소들은 각각 떨어진 메모리 공간에 존재합니다 ), 각 원소들은 pointer를 통해 연결되어있습니다.

 

https://www.geeksforgeeks.org/doubly-linked-list/ 출처

2. Linked List의 구현

 

실제 데이터를 담고있는 Node 와, Node들의 연결체인 Linked List의 구현으로 나뉩니다.

각각의 Node는 이전Node인 prev, 다음 Node인 next 라는 포인터변수를 가지고 있습니다.

 

Linked List는 가장 앞 Node인 head와 가장 뒷 Node인 tail를 가지고 있습니다.

또한, Linked list에 node를 삽입해주는 함수인 add 와, 특정 Node를 지워주는 함수인 remove 함수를 갖고 있습니다.

 

 

Linked list의 add 함수의 경우, 

Linked list의 가장 마지막 Node 인 tail 의 다음 Node에 들어올 Node를 붙혀주어야 합니다.

단, Linked List에 아무런 Node가 없을 경우 처음 들어온 Node 가 Linked list의 처음이자 마지막 Node가 됩니다.

 

 

Linkedlist의 remove 함수의 경우,

해당 Node를 지우는 함수입니다. 단 Node 를 지울 경우, 지울 Node 의 prev 와 next를 연결해주고 지워야 합니다.

https://www.cpp.edu/~ftang/courses/CS240/lectures/dlist.htm 출처

그림을 잘 살펴보세요.

 

그림을 보면 지울 Node 기준으로,

지울Node 이전Node의 next 값은 지울Node의 다음 Node 가 됩니다.

지울Node 다음Node의 prev 값은 지울Node의 이전 Node 가 됩니다.

 

코드로 구현 하면 위와 같이 되겠군요 !

 

 

3. Code

 

 

#include <iostream>

using namespace std;

class Node {
    public:
        int data;
        Node* prev;
        Node* next;
        Node(int data);
};


Node::Node (int data) {
    this->data = data;
}

class LinkedList {
    public:
        Node* head;
        Node* tail;
        void add(Node*);
        void remove(Node*);
        void print();
};

void LinkedList::add(Node* node) {

    // When input node is the first node of the linked list
    if ( this->head == NULL && this->tail == NULL ) {
        this->head = node;
        this->tail = node;
        return ;
    } 
    
    // When there are nodes that previously added in linked list.
    this->tail->next = node;
    node->prev = this->tail;
    this->tail = node;
}


// When we want to remove node,
// update head and tail if removed node is head or tail,
// and connect prev node and next node,
// then remove current node.
void LinkedList::remove(Node* node){
    
    if ( node == head ) {
        head = node->next;
    } 

    if ( node == tail ) {
        tail = node->prev;
    }

    if( node->prev != NULL ) {
        node->prev->next = node->next;
    }

    if( node->next != NULL ) {
        node->next->prev = node->prev;
    }

    delete node;
}

void LinkedList::print() {
        Node* node = this->head;
    while(node != NULL) {
        cout << node->data << ' ';
        node = node->next;
    }
    return ;
}

int main () {
    LinkedList* list = new LinkedList();
    for( int i = 0; i < 7; i++ ) {
        Node* node = new Node(i);
        list->add(node);
    }
    list->print();
}