양방향 연결리스트 (Doubly linked list)

양방향 연결리스트 

 

삽입

- 가장 초기 상태의 삽입은 head와 tail 만 있으며 새로운 노드가 삽입이 된다(head,tail은 data 값이 존재하지 않는다)

 

 

삭제

#include <stdio.h>
#include <stdlib.h>
struct Node
{
	int data;
	Node* prev;
	Node* next;
};

Node *head, *tail;

void Insert(int data)
{
	Node *node = (Node*)malloc(sizeof(Node));
	node->data = data;
	Node *cur = head->next;
	while (cur->data < data && cur != tail)
	{
		cur = cur->next;
	}
	// cur->prev->next 이러면 지저분 해지니 prev 변수 생성
	Node *prev = cur->prev;
	prev->next = node;
	node->prev = prev;
	cur->prev = node;
	node->next = cur;
}

void RemoveFront()
{
	// 보통 Remove 시에는 cur이름을 안쓰는 것 같음
	Node *node = head->next;
	head->next = node->next;
	// node->next->prev 이러면 좀 지저분 해지니 next 변수 생성
	Node *next = node->next;
	next->prev = head;
	free(node);
}

void Show()
{
	Node *cur = head->next;
	while (cur != tail)
	{
		printf("%d ", cur->data);
		cur = cur->next;
	}
}


int main()
{
	head = (Node*)malloc(sizeof(Node));
	tail = (Node*)malloc(sizeof(Node));
	head->prev = head;
	head->next = tail;
	tail->prev = head;
	tail->next = tail;
	Insert(3);
	Insert(4);
	Insert(1);
	Insert(1);
	Insert(7);
	Insert(8);
	Insert(3);
	RemoveFront();
	RemoveFront();
	RemoveFront();

	Show();

	return 0;
}

 

해당 소스는 head와 tail 사이의 노드에 오름차순으로 값을 삽입한 과정이다

 

*그림 및 소스는 패스트캠퍼스 자료구조 양방향 연결리스트 강좌 참고