양방향 연결리스트(삽입, 삭제 함수)

양방향 연결리스트

• 머리와 꼬리를 모두 가짐
• 리스트의 앞 뒤 모두 접근 가능
• 메모리 공간을 더 사용함(단방향에 비해)

 

삽입 함수

• 앞 노드의 next가 새 노드의 prev를 가리킴
• 새 노드의 prev가 앞 노드의 next를 가리킴
• 뒷 노드의 prev가 앞 노드의 next를 가리킴
• 새 노드의 next가 뒷 노드의 prev를 가리킴

void insert(int data)
{
    Node *node = (Node *)malloc(sizeof(Node));
    node->data = data;

    Node *cur;
    cur = head->next;
    while (cur->data < data && cur != tail)
    {
        cur = cur->next;
    }

    Node *prev = cur->prev;
    prev->next = node;
    node->prev = prev;
    cur->prev = node;
    node->prev = cur;
}

 

맨 앞 원소 삭제

• head 의 next가 삭제할 노드의 next를 가리킴
• 삭제할 노드의 다음 노드의 prev가 head의 next를 가리킴
• 삭제할 노드 메모리 해제

void    remove_front()
{
    Node *node = head->next;
    head->next = node->next;

    Node *next = node->next;
    next->prev = head;
    free(node);
}

 

main문

int        main()
{
    head = (Node*)malloc(sizeof(Node));
    tail = (Node*)malloc(sizeof(Node));
    head->next = tail;
    head->prev = head; //definition of first node
    tail->next = tail; //definition of last node
    tail->prev = head;
    ...
}

주의사항

• 삽입 삭제 기능에서 예외사항 처리 필요
• 삭제할 원소가 없는데 삭제하는 경우 체크 필요