이중 연결 리스트

📌 이중 연결 리스트

💡 이중 연결 리스트의 개념

1. 이중 연결 리스트(Double Linked List)란?
   1. 한 노드에 두 개의 Link 가 저장
   2. 이중 연결 리스트는 양방향으로 이동가능
      1. 단일 연결 리스트의 경우, 한 방향으로만 이동이 가능.

struct node{
    struct node *llink; // 이전 노드 포인트
    int data;
    struct node *rlink; // 다음 노드 포인트

💡 이중 연결 리스트의 종류

1. 체인
   1. 처음 노드의 llink와 마지막 노드의 rlink는 NULL
   2. ptr = ptr -> llink -> rlink = ptr -> rlink -> llink

2. 원형 이중 연결 리스트

3. 원형 이중 연결리스트에 노드를 추가하는 방법
   1. 새로 추가되는 링크의 노드를 먼저 바꾸는 것이 좋다.

      void dinsert(struct node *node, struct node *newnode){
        # newnode를 node의 오른쪽에 추가
        newnode -> llink = node;
        newnode -> rlink = node -> rlink;
        node -> rlink -> llink = newnode;
        node -> rlink = newnode;
      }

4. 원형 이중 연결 리스트에서 노드 삭제

   void ddelete(struct node *deleted){
    deleted -> llink -> rlink = delete -> rlink;
    deleted -> rlink -> llink = delete -> llink;
    free(delete);
   }