[c++][자료구조] Double Linked List(더블 링크드 리스트) 구현 / List STL

◎ next , prev 두개의 노드 포인터를 가지고 있다.

◎ Single Linked List에 비해 함수 처리가 더 용이하고 접근성이 더 뛰어나다.

◎ 맨 앞에는 head 노드 , 맨 뒤에는 tail 노드가 있다.

◎ 삽입 / 삭제가 빠르다.

 

구현

 

구조체

 

1) Node Struct

struct Node{
    int data; // data in Node.
    Node* prev; // pointing before Node.
    Node* next; // pointing after Node.
};

using pNode = Node*;

 

2) List Struct

struct List{
    Node* head; // front of list.
    Node* tail; // end of list.

    List(){
        head = new Node{};
        tail = new Node{};
        head->next = tail;
        tail->prev = head;
    }
    ~List(){}
};

using pList = List*;

List가 맨 앞에 head 노드와 맨 뒤에 tail 노드로 감싸여져 있는 형태이다.

 

 

함수

 

support 함수들

 

begin : head 다음 노드 (list 첫 번째 노드) 반환.

pNode begin(pList p){
    return p->head->next;
}

 

end : tail 노드 반환

pNode end(pList p){
    return p->tail;
}

 

last : tail 이전 노드 반환

pNode last(pList p){
    return end(p)->prev;
}

 

empty : 비어있다면 true , 아니라면 false 반환.

bool empty(pList p){
    return begin(p)==end(p);
}

 

메인 함수들

 

size : list 노드 갯수 반환. (head , tail 노드 제외)

int size(pList p){
    int cnt = 0;
    
    if(empty(p)) return cnt;

    for(pNode n = begin(p) ; n!=end(p) ; n = n->next){
        cnt++;
    } 

    return cnt;
}

 

 

find : val 값을 data로 지닌 node를 찾아서 return.

pNode find(pList p , int val){
     
    for(pNode n = begin(p) ; n!= end(p) ; n = n->next){
        if(n->data == val) return n;
    }
    return nullptr;
}

 

 

insert : x 노드 앞에 val 값을 가진 노드 삽입.

void insert(pNode x , int val){
    pNode node = new Node{val, x->prev , x};
    x->prev->next = node;
    x->prev = node;
}

 

 

push / pop

 

 

push_front : head 다음에 새로운 노드 삽입.

void push_front(pList p , int val){
    insert(begin(p), val);
}

 

 

push_back : tail 앞에 val 값을 가진 노드 삽입.

void push_back(pList p , int val){
    insert(end(p) , val);
}

 

 

pop_front : head 다음 노드(List 첫 번째 노드) 삭제

void pop_front(pList p){
    if(!empty(p)) erase(begin(p));
    else{
        cout << "It doesn't work. List is empty." << endl;
    }
}

 

 

pop_back : tail 이전 노드 삭제.

void pop_back(pList p){
    if(!empty(p)) erase(last(p));
    else{
        cout << "It doesn't work. List is empty." << endl;
    }
}

 

 

print_all : list 모든 노드 값 출력.

void print_all(pList p){
    for(pNode n = begin(p) ; n != end(p) ; n = n->next){
        cout << n->data << ' ';
    }
    cout << endl;
}

 

 

erase : n 노드 삭제.

void erase(pNode n){
    n->next->prev = n->prev;
    n->prev->next = n->next;
    delete n;
}

void erase(pList p , pNode n){
    if(n == end(p) || n == p->head) return;
    erase(n);
}

 

오버라이딩을 통해 n 노드가 존재 하지 않는다면 강제종료 시키는 장치 설정.

 

 

unique : sorted 된 list에서 중복된 data를 가진 node들이 있으면 하나만 남기고 삭제.

void unique(pList p){
    if(size(p) <= 1 ) return;

    for(pNode n = begin(p) ; n != end(p) ; n = n->next){
        if(n->data == n->prev->data){
            n = n->prev;
            erase(p,n->next);
        }
    }
}

 

 

응용 함수들

 

reverse : 노드 순서를 거꾸로 만들기.

 

void reverse(pList p){

    if(size(p) <= 1) return;
    
    pNode n = begin(p);
    pNode next_node = begin(p)->next;
    while(n != end(p)){
        n->next = n->prev;
        n->prev = next_node;
        n = next_node;
        next_node = next_node->next;
    }

    p->head->prev = p->head->next;
    p->tail->next = p->tail->prev;
    p->head->next = nullptr;
    p->tail->prev = nullptr;
    pNode temp = p->head;
    p->head = p->tail;
    p->tail = temp;

}

 

 

 

half : 가운데 있는 노드 반환

pNode half(pList p){
    if(empty(p)) return nullptr;

    pNode rabbit = p->head;
    pNode turtle = p->head;

    while(rabbit != end(p)){
        turtle = turtle->next;
        rabbit = rabbit->next;
        if(rabbit == end(p)){
            break;
        }
        rabbit = rabbit->next;
    }

    return turtle;
}

rabbit이 두 칸 갈때 turtle은 한 칸 이동한다.

이 알고리즘을 통해 가운데 있는 노드를 찾는다.

 

---

 

STL

 

◎ <List> STL은 double linked list를 기반으로 구현 된 container 이다.

◎ <vector> 와 함께 굉장히 많이 사용되는 STL이다.

 

자세한 STL은 아래 글에 정리가 되어있다.

아래 글을 참고하자.

2022.02.13 - [c++/문법] - [c++][자료구조] Vector / List 비교 및 STL 정리

[c++][자료구조] Vector / List 비교 및 STL 정리