Double linked list

  • Single linked list에서는 추가된 노드가 항상 뒤쪽으로만 추가됨. prev만 가지고 있음
  • Double linked list는 Head와 Tail 두개의 Node를 미리 가지고 있음. 각 노드는 prev와 next도 가지고 있음
NODE* head = myalloc();
NODE* tail = myalloc();
head->next = tail;
tail->prev = head;
  • 초기화로, head의 next는 tail을, tail의 prev는 head를 가리키고 있음. tail->prev가 싱글링크드리스트의 pList역할을 하고 있음
  • 노드를 추가 하는 경우, 기존 싱글링크드리스트의 prev처리와 함께 새로 next처리도 해주면 됨. 그림 그려보며 이해하기
//single linked list와 동일
NODE* node1 = myalloc();
node1->v = 1;

node1->prev = tail->prev;
tail->prev = node1;

//next의 연결
node1->next = node1->prev->next;
node1->prev->next = node1;

//반복
NODE* node2 = myalloc();
node2->v=2;

node2->prev = tail->prev;
tail->prev = node2;

node2->next = node2->prev->next;
node2->prev->next = node2;
  • 이제 검색할때 head에서 tail까지 혹은 tail에서 head까지 검색 할 수 있음
//head에서 tail까지
for(NODE* it = head->next; it != tail; it = it->next){
    if(it->v == 1) cout<<"FOUND"<<endl;
}

//tail에서 head로
for(NODE* it = tail->prev; it != head; it= it->prev){
    if(it->v ==1) cout<<"FOUND"<<endl;
}
  • 삭제 하는 법은 노드의 연결만 변경하면 됨
//값이 2인 노드 삭제하기
for(NODE* it = head->next; it != tail; it= it->next){
    if(it->v ==2){
        it->prev->next = it->next; //prev 노드의 next를 내가 가리키던 next로 연결
        it->next->prev = it->prev; //next 노드의 prev를 내가 가리키던 prev로 연결
    }
}
  • Single linked list에서도 dummy node인 Tail노드를 미리 만들어 두고 사용하면 노드 삭제가 좀더 쉬움
#include <iostream>
using namespace std;

struct NODE {
    int v;
    NODE* prev;
}a[10000];

int idx = 0;

NODE* myalloc() {
    return &a[idx++];
}

int main() {
    //init
    idx = 0;

    NODE* tail = myalloc();//dummy tail node
    tail->prev = nullptr;//tail->prev가 plist역할을 대신함

    NODE* p;
    for (int i = 0; i < 8; ++i) {
        p = myalloc();
        p->v = i;
        p->prev = tail->prev;
        tail->prev = p;
    }

    //노드 추가된 것 확인
    for (NODE* it = tail->prev; it != nullptr; it = it->prev) {
        cout << it->v << endl;
    }

    //5를 찾아서 삭제
    NODE* next = tail;
    for (NODE* it = tail->prev; it != nullptr; it = it->prev) {
        if (it->v == 5) {
            cout << "Deleted " << it->v << endl;
            next->prev = it->prev;//여기서 next는 node6 아직 가리키고 있다가 it(node5)가 가리키던 node4를 가리키게바꿈 
        }
        next = it;//노드를 저장, next가 it보다 하나씩 늦게 이동하면서 prev가 아닌 next방향의 노드를 참조할수 있게 해줌
    }

    //노드 삭제 된 것 확인
    for (NODE* it = tail->prev; it != nullptr; it = it->prev) {
        cout << it->v << endl;
    }

    cout << tail->prev->v << endl;

    return 0;
}

 

You may also like...