[15] C review < 이중연결리스트 > 과제 수정 필요

단방향 연결 리스트(single linked list)의 한계 

- 어떤 노드의 앞에 새로운 노드를 삽입하기 어려움

- 삭제의 경우에 항상 삭제할 노드의 앞 노드가 필요

- 단방향의 순회만이 가능 

 

이중 연결 리스트 

- 각각의 노드가 다음(next)노드와 이전(previous)노드의 주소를 가지는 연결 리스트 

- 양방향의 순회(traverse)가 가능.

 

각 노드에 하나의 문자열이 저장된다고 가정하자.

#include<stdio.h>
#include<stdlib.h>

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

typedef struct node Node;

Node *head;
Node *tail;
int size = 0;

노드를 삽입하는 경우를 알아봅시다. 이 과정은 순서가 매우 중요합니다. 

삭제할때는 해당노드에 바로 접근하여 삭제하면 됩니다. 

 

< 추가할때 여려 경우의 수 >

1. 비어있는 리스트에서 처음 노드 삽입하기 

2. 맨 앞에 노드 삽입하기 

3. 맨 끝에 노드 삽입하기 

4. 중간에 노드 삽입하기

 

< 삭제할때 여려 경우의 수 >  과제.

1. p가 유일한 노드인 경우

 

2. p가 head인 경우

 

3. p가 tail인 경우

 

4. 그밖의 일반적인 경우 

 

 

< 정렬된 상태에서의 추가 >

뒤에서부터 순회