*자료구조 제 11강 (이중연결리스트)

단방향 연결 리스트의 한계

• 어떤 노드의 앞에 새로운 노드를 삽입하기 어려움
• 삭제의 경우에 항상 삭제할 노드의 앞 노드가 필요
• 단방향의 순회만이 가능

이중 연결 리스트

• 각각의 노드가 다음 노드와 이전 노드의 주소를 가지는 연결 리스트
• 양방향의 순회 가능

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

typedef struct node Node;

Node* head;
Node* tail;
int size = 0;		//연결리스트의 노드의 개수

 

 

노드 삽입

Node* new_node = (Node*)malloc(sizeof(Node));		//새로운 노드 생성
new_node->data = "Sharon";
new_node->next = p;
new_node->prev = p->prev;
p->prev->next = new_node;
p->prev = new_node;

 

노드 삭제

p->prev->next = p->next;
p->next->prev = p->prev;

고려해야하는 경우

1. 삭제할 노드가 연결리스트의 유일한 노드인 경우 -> head, tail이 모두 NULL이 되어야 함
2. head 노드인 경우 -> head값 변경되어야 함
3. tail 노드인 경우 -> tail값 변경되어야 함
4. 일반적인 head, tail도 아닌 경우 -> head, tail 변경X

-> 수정 결과

//수정해서 첨부 예정

 

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;

	if (pre == NULL && head == NULL) {		//empty 리스트인 경우
		head = new_node;
		tail = new_node;
	}
	else if (pre == NULL) {					//pre는 NULL이고, head는 NULL이 아닌 경우
		new_node->next = head;
		head->prev = new_node;
		head = new_node;
	}
	else if (pre == tail) {
		new_node->prev = tail;
		tail->next = new_node;
		tail = new_node;
	}
	else {							//head도 tail도 아닌 중간에 넣는 경우
		new_node->prev = pre;
		new_node->next = pre->next;
		pre->next->prev = new_node;
		pre->next = new_node;
	}
	size++;
}

 

void add_ordered_list(char* item) {
	Node* p = tail;
	while (p != NULL && strcmp(item, p->data) < 0)	//연결리스트 역방향 순회하면서 검사
		p = p->prev;
	add_after(p, item);
}

 

원형 연결리스트

• 마지막 노드의 다음 노드가 첫번째 노드가 되는 단순 연결리스트

원형 이중연결 리스트

• 마지막 노드의 다음 노드가 첫번째 노드가 되고
• 첫 노드의 이전 노드가 마지막 노드가 됨