이중 연결 리스트 (Doubly Linked List)
이중 연결 리스트는 이전과 다음 링크 필드를 2개 가지는 연결 리스트이다
이전과 다음 링크 필드가 2개라 양방향으로 데이터 탐색이 가능하다
생성
이중 연결 리스트 정의
typedef int Data; // 노드 안에 저장할 Data 정의
typedef struct // 노드 내부 정의
{
Data data;
struct Node *Prev, *Next;
} Node;이중 연결 리스트 생성
Node *head = NULL;
head = (Node *)malloc(sizeof(Node));
head -> data = 10;
head -> Next = NULL;
head -> Prev = NULL;위의 코드처럼 첫 노드를 생성하면 아래 그림과 같다
삽입
이중 연결 리스트도 단순 연결 리스트처럼 삽입할 때 맨 앞에 삽입, 중간이나 마지막에 삽입 이렇게 두가지로 나뉜다
맨 앞에 삽입
Node* insert_first(Node *head, Data value)
{
Node *p = (Node*)malloc(sizeof(Node)); // p라는 새로운 노드 생성
p -> data = value;
p -> Next = head; // ①
p -> Prev = NULL; // ②
if (head != NULL) head -> Prev = p; // ③
head = p; // ④
return head;
}
중간이나 맨 뒤에 삽입
// 노드 q 뒤에 새로운 노드 p 삽입
Node* insert(Node *head, Node *q, Data value)
{
Node *p = (Node *)malloc(sizeof(Node));
p -> data = value;
p -> Next = q -> Next; // ① q가 마지막 노드이면 p -> Next = NULL
p -> Prev = q; // ②
if (q -> Next != NULL) q -> Next -> Prev = p; // ③
q -> Next = p; // ④
return head;
}
중간이나 맨 뒤에 삽입하는 경우, q가 마지막 노드이면 ①에서 p -> Next에 NULL 값이 저장되고 ③이 생략된다
삭제
// p 노드를 삭제
Node* delete(Node *head, Node *p)
{
if (p -> Next != NULL) p -> Next -> Prev = p -> Prev; // ①
if (p -> Prev != NULL) p -> Prev -> Next = p => Next; // ②
else head = p -> Next; // p가 맨 처음 노드일 때
free(p);
return head;
}
삭제할 노드를 검정 사각형이라고 가정하면 아래와 같이 4가지로 경우를 나눌 수 있는데, 상기 코드로 네 경우를 커버할 수 있다
① □ - ■ - □ : 삭제할 노드가 노드들 중간에 있는 경우
② head - ■ - □ : 삭제할 노드가 첫 번째 노드 + 다음 노드가 존재할 경우
③ □ - ■ - NULL : 삭제할 노드가 마지막 노드인 경우
④ head - ■ - NULL : 삭제할 노드가 첫 번째 노드 + 다음 노드가 없을 경우
순환 이중 연결 리스트 (Circular Doubly Linked List)
이중 연결 리스트도 순환시킬 수 있다
순환 이중 연결 리스트의 구현을 그림으로 표현하면 다음과 같으며, 마지막 노드의 다음 링크 필드를 첫 번째 노드를 가리키게 하면 완성 된다
어 그런데 위의 그림을 잘 보면 이제까지 배웠던 연결 리스트와 다른 점이 존재한다
헤드 포인터가 없다는 점이다
그럼 순환 이중 연결 리스트는 헤드 포인터를 사용할 수 없다는 것인가?
그런건 아니다
순환 이중 연결 리스트도 헤드 포인터를 사용하고 첫 번째 노드의 이전 링크 필드를 마지막 노드를 가리키게하여 구현할 수도 있다
위와 같은 순환 이중 연결 리스트를 헤드 노드를 이용하여 구현하면 삽입, 삭제 시 경우를 나누지 않아 코드가 간단해지는 장점이 있다
삽입
// 노드 q 뒤에 새로운 노드 p 삽입
Node* insert(Node *head, Node *q, Data value)
{
Node *p = (Node *)malloc(sizeof(Node));
p -> data = value;
p -> Next = q -> Next; // ①
p -> Prev = q; // ②
q -> Next = p; // ③
p -> Next -> Prev = p; // ④
return head;
}삭제
// p 노드를 삭제
Node* delete(Node *head, Node *p)
{
p -> Next -> Prev = p -> Prev; // ①
p -> Prev -> Next = p => Next; // ②
free(p);
return head;
}
마지막으로 이중 연결 리스트의 장단점을 알아보면
장점 : 단순 연결 리스트의 장점 + 양방향성
단점 : 링크 필드가 2개라 추가적인 메모리 소모가 존재