[자료구조] 양방향 연결 리스트

양방향 연결 리스트

• 머리(Head)와 꼬리(Tail)를 모두 가짐

• 각 노드는 앞 노드와 뒤 노드의 정보를 모두 저장

양방향 연결 리스트

 

양방향 연결 리스트 삽입 과정

 

양방향 연결 리스트 삭제 과정

 

데이터를 오름차순으로 저장하는 양방향 연결 리스트 구현

typedef struct
{
	int data;
	struct Node *prev;
	struct Node *next;
} Node;

Node *head, *tail;

void Insert( int data )
{
	Node* node = (Node*)malloc(sizeof(Node));
	node->data = data;
	Node* cur;
	cur = head->next;
	while( cur->data < data && cur != tail )
	{
		cur = cur->next;
	}
	Node* prev = cur->prev;
	prev->next = node;
	node->prev = prev;
	cur->prev = node;
	node->next = cur;
}

void RemoveFront()
{
	Node* node = head->next;
	head->next = node->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(void)
{
	head = (Node*)malloc(sizeof(Node));
	tail = (Node*)malloc(sizeof(Node));
	head->next = tail;
	head->prev = head;
	tail->next = tail;
	tail->prev = head;
	Insert(2);
	Insert(1);
	Insert(3);
	Insert(9);
	Insert(7);
	RemoveFront();
	Show();
	system("pause");
	return 0;
}

결과
2 3 7 9

장점 : 리스트의 앞 혹은 뒤에서부터 모두 접근할 수 있다.

단점 : 단방향 연결 리스트에 비해서 메모리 공간을 많이 먹는다.

 

양방향 연결 리스트 구현에 있어 주의할 점

• 삽입 및 삭제 기능에서의 예외사항을 처리할 필요가 있음

  • 더 이상 삭제할 원소가 없는데 삭제하는 경우 등