13. 이중 연결리스트

지금까지 단일 연결리스트를 공부해 왔다.

단일 연결리스트는 이전 노드로 갈 수 없다는 단점이 존재하여 이전 노드로 돌아갈 수 있도록 원형으로 구성하여 어떤 노드든 참조가 가능할 수 있도록 하였다.

하지만, 현재 노드에서 바로 이전 노드를 참조하려 할 때는 모든 노드를 거쳐야 한다는 불편한 점이 존재한다.

---

이중 연결리스트란?

이중 연결리스트는 각 노드가 이전 노드와 다음 노드를 가리키는 포인터를 가진 연결리스트이다.

이전 노드와 다음 노드를 모두 가리키기 때문에 양방향 탐색이 가능하며 삽입, 삭제가 용이하다.

---

노드의 구조체 정의

단일 연결리스트와는 다르게 포인터가 2개 있는 것을 확인할 수 있다.

// 노드에 대한 구조체 정의
typedef struct Node *NodePointer;
typedef struct Node{
    int data;
    NodePointer prev;
    NodePointer next;
}Node;

---

노드 삽입 함수

리스트가 비어있는 경우, 맨 앞, 맨 뒤,  n번째 위치에 삽입하는  경우로 나뉘어 함수가 동작하게 된다.

// 노드를 생성하여 연결리스트 position번째에 삽입한다.
NodePointer Insert_Node(NodePointer head, int data, int position){
    int i;
    NodePointer temp = head;
    NodePointer New_Node = (NodePointer)malloc(sizeof(Node));
    New_Node -> data = data;
    
    // 연결리스트가 비어있는 경우
    if(!head){
        New_Node->prev = NULL;
        New_Node->next = NULL;
        return New_Node;
    }
    
    // 리스트 맨 앞에 삽입하는 경우
    if(!position){
        New_Node -> prev = NULL;
        New_Node -> next = head;
        head -> prev = New_Node;
        return New_Node;
    }
    
    
    for(i=0;i<position-1;i++){
        if(!(temp->next)) { // 리스트 끝에 도달한 경우
            New_Node->prev = temp;
            New_Node->next = NULL;
            temp->next = New_Node;
            return head;
        }
        temp = temp->next;
    }
    
    New_Node->next = temp->next;
    New_Node->prev = temp;
    temp->next->prev = New_Node;
    temp->next = New_Node;
    return head;
}

---

노드 삭제 함수

리스트의 맨 앞, 맨 뒤, n번째 위치에 노드를 삭제하는 경우로 나뉘어 함수가 동작하게 된다.

NodePointer Delete_Node(NodePointer head, int position){
    int i;
    NodePointer temp2, temp = head;
    
    // 맨 앞을 삭제하는 경우
    if(position <= 1){
        head = head->next;
        if(!head) head->prev = NULL;
        free(temp);
        return head;
    }
    
    for(i=0;i<position-1 && temp->next;i++) temp = temp->next;
    
    // 맨 뒤를 삭제하는 경우
    if(!temp->next){
        temp2 = temp->prev;
        temp2->next = NULL;
        free(temp);
    }
    else{ // 중간을 삭제하는 경우
        temp2 = temp->prev;
        temp2->next = temp->next;
        temp->next->prev = temp2;
        free(temp);
    }
    return head;
}

삽입 삭제 함수의 경우 포인터를 조정하는 부분의 순서가 달라지는 경우 정상동작이 불가능 해 질 수 있으므로 어떤 부분 순서를 주의해야 하는지 알아둬야 한다.