[자료구조 - C언어] 자료구조 제13강: 이중 연결 리스트

//공부 기록용 포스팅입니다. 틀린 부분이 있을 경우 댓글로 알려주시면 감사합니다! 😎

 

 

1. 단방향 연결 리스트와 이중 연결 리스트

• 단방향 연결 리스트(single linked list)
  • 어떤 노드의 앞에 새로운 노드를 삽입하기 어려움
  • 삭제할 노드의 앞 노드가 필요함
  • 단방향 순회만 가능
• 양방향 연결 리스트(double linked list) = 이중 연결 리스트
  • 양방향 순회가 가능
  • 각각의 노드가 다음(next) 노드와 이전(previous) 노드의 주소를 가지는 연결 리스트

 

2. 양방향 연결 리스트의 Node

struct node{
    char *data;
    struct node *next;
    struct node *prev;
};
typedef struct node  Node;

Node *head;   //연결리스트의 첫 번째 노드 주소 저장
Node *tail;      //연결리스트의 마지막 노드 주소 저장
int size=0;    //현재 노드 개수

 

3. 어떤 노드 앞에 노드 삽입

• 단방향 연결 리스트에서는 노드를 중간에 삽입하려면
  • 앞 노드의 주소를 통해 → 그 노드의 바로 뒤에 삽입할 수 있었다.
• 양방향 연결 리스트에서는 prev와 next를 통해 어떤 노드의 앞에 노드를 삽입할 수 있다.

//어떤 노드 앞에 노드 삽입
//1. 새로운 노드 생성
Node *new_node = (Node *)malloc(sizeof(Node));
new_node->data = "by";
  
//2. 새로운 노드의 링크를 먼저 연결
new_node->next = p;
new_node->prev = p->prev;
    
//3. 노드의 앞 뒤 노드 링크 정리
p->prev->next = new_node;
p->prev = new_node;

3-1. add_after(Node *pre, char *item)

• case
  • empty 리스트
  • 제일 앞/뒤
  • 중간

void add_after(Node *pre, char *item){
    //새 노드 생성
    Node *new_node = (Node*)malloc(sizeof(Node));
    new_node->data = item;
    new_node->prev = NULL;
    new_node->next = NULL;
    
    //연결리스트에 노드가 하나도 없는 empty list인 경우
    //head==NULL이면 empty list
    //empty list 이기 때문에 pre도  NULL
    if(pre==NULL && head==NULL){
        //삽입하는 새 노드가 유일한 노드
        //첫 번째이자 마지막 노드
        head=new_node;
        tail=new_node;
    }

    //맨 앞에 삽입하는 경우
    //head!=NULL일 때 pre==NULL이면 제일 앞에 삽입
    else if(pre==NULL){
        //새로운 노드의 다음 노드는 지금 head가 가리키는 노드
        new_node->next=head;
        //현재 head가 가리키는 노드의 앞 노드는 새로운 노드
        head->prev = new_node;
        //head가 새로운 노드를 가리키게 함
        head=new_node;
    }

    //맨 마지막에 삽입하는 경우
    else if(pre==tail){
        //새로운 노드의 앞 노드는 맨 마지막 노드
        new_node->prev = tail;
        //원래 맨 마지막이었던 노드의 뒤에 새로운 노드 연결
        tail->next = new_node;
        //tail이 새로운 노드를 가리키게 함
        tail = new_node;
    }

    //중간 삽입
    else{
        new_node->prev=pre;
        new_node->next=pre->next;
        pre->next->prev=new_node;
        pre->next=new_node;
    }
    size++;
}

 

4. 노드 삭제

• 단방향 연결 리스트에서 노드를 삭제하기 위해서는 앞 노드의 주소가 필요하지만
  • 양방향 연결 리스트에서는 삭제하고자 하는 노드만 필요로 한다.
   

//노드 삭제
p->prev->next = p->next;
p->next->prev = p->prev;

4-1. remove(Node *p)

• p가 유일한 노드
  • head=NULL, tail=NULL
• p가 head
  • head만 수정
• p가 tail
  • tail만 수정
• 중간 삽입 ~ head와 tail은 변경 X

void remove(Node *p){
    //p가 유일한 노드인 경우
    if(head==p && tail==p){
        head=NULL;
        tail=NULL;
        free(p);
    }
    //p가 head인 경우
    else if(head==p){
        p->next->prev=NULL;
        head=p->next;
        free(p);
    }
    //p가 tail인 경우
    else if(tail==p){
        p->prev->next=NULL;
        tail=p->prev;
        free(p);
    }
    //중간 삭제
    else{
        p->prev->next=p->next;
        p->next->prev=p->prev;
        free(p);
    }
}

 

5. add_ordered_list(char *item)

• add_after을 사용해서 정렬된 위치에 노드를 삽입하는 함수
• 역방향으로 순회를 해서 처음으로 ‘보다 작은’ 노드를 찾고, 그 뒤에 삽입(add_after)

//add_after을 사용해서
//정렬된 위치에 노드를 삽입하는 함수
//역방향 순회 ~ 처음으로 '보다 작은'노드를 찾고 그 뒤에 삽입
void add_ordered_list(char *item){
    Node *p = tail;
    //item보다 p->data가 클 동안
    while(p!=NULL && strcmp(p->data, item)<0)
        //앞으로 이동
        p=p->prev;
    add_after(p, item);
}

• empty list
  • p도 NULL, head도 NULL ~ add_after의 첫 번째 조건에 해당
• 가장 큰 입력값(= 마지막에 삽입)
  • p는 tail, head는 NULL 아님 ~ add_after의 세 번째 조건에 해당
• 가장 작은 입력값(= 처음에 삽입)
  • p는 NULL ~ add_after의 두 번째 조건에 해당

 

6. 원형(circular) 리스트

• 원형 연결 리스트
  • 마지막 노드의 다음 노드가 첫 번째 노드가 되는 단순 연결 리스트
• 원형 이중 연결 리스트
  • 마지막 노드의 다음 노드가 첫 번째 노드가 되고
  • 첫 노드의 이전 노드가 마지막 노드가 됨

 

 

 

 

---

부경대학교 권오흠 교수님의 [c로 배우는 자료구조 및 여러 가지 예제 실습] 강의 정리입니다. 감사합니다.

https://www.youtube.com/watch?v=0FlCrw3B4mE&t=2344s