본문으로 바로가기

자료구조 공부#15 (연결리스트3)

category 이론공부/자료구조 2021. 4. 22. 12:18

2021.04.20 - [이론공부/자료구조] - 자료구조 공부#14 (연결리스트2)

이전내용을 참고하자


 

이중 연결 리스트

 

한 노드에 앞 선행노드링크, 후속노드링크 두개를 가지고 있음

 

단순 연결리스트, 원형 연결리스트의 단점인 선행 노드를 찾기가 힘든걸 극복해낸 리스트.

하나의 노드가 선행 노드, 후속 노드에 대한 링크를 가지고 있음

 

단점 : 공간을 많이 차지하고 코드가 복잡해짐

 

헤드노드

헤드노드엔 데이터가 없다

데이터를 가지지 않고, 삽입, 삭제 코드를 간단하게 할 목적으로 만들어진 노드.

헤드 포인터와의 구병리 필요

공백상태에서는 헤드 노드만 존재함.

 

typedef int element;
typedef struct DListNode{
	element data;
    struct DListNode* llink;
    struct DListNode* rlink;
}

 

 

삽입연산

삽입연산

 

void dinsert(DListNode* before, element data) {
	DListNode* newnode = (DListNode*)malloc(sizeof(DListNode));
	newnode->data = data; //데이터 삽입
	newnode->llink = before;		//(1)
	newnode->rlink = before->rlink;	//(2)
	before->rlink->llink = newnode;	//(3)
	before->rlink = newnode;		//(4)
}

 

 

삭제연산

 

void ddelete(DListNode* head, DListNode* removed) {
	if (removed == head)return;
	removed->llink->rlink = removed->rlink;
	removed->rlink->llink = removed->llink;
	free(removed);
}

 

 

더보기
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef int element;
typedef struct DListNode {
	element data;
	struct DListNode* llink;
	struct DListNode* rlink;
}DListNode;

void init(DListNode* phead) {
	phead->llink = phead;
	phead->rlink = phead;
}

void print_dlist(DListNode* phead) {
	DListNode* p;
	for (p = phead->rlink; p != phead; p = p->rlink) {
		printf("%<-| |%d| |->", p->data);
	}
	printf("\n");
}

void dinsert(DListNode* before, element data) {
	DListNode* newnode = (DListNode*)malloc(sizeof(DListNode));
	newnode->data = data; //데이터 삽입
	newnode->llink = before;		//(1)
	newnode->rlink = before->rlink;	//(2)
	before->rlink->llink = newnode;	//(3)
	before->rlink = newnode;		//(4)
}

void ddelete(DListNode* head, DListNode* removed) {
	if (removed == head)return;
	removed->llink->rlink = removed->rlink;
	removed->rlink->llink = removed->llink;
	free(removed);
}



int main(void) {
	DListNode* head = (DListNode*)malloc(sizeof(DListNode));
	init(head);
	printf("추가단계\n");
	for (int i = 0; i < 5; i++) {
		dinsert(head, i);
		print_dlist(head);
	}
	printf("삭제단계\n");
	for (int i = 0; i < 5; i++) {
		print_dlist(head);
		ddelete(head, head->rlink);
	}
	free(head);


	return 0;
}

 

 


느낀점 ; 앞에 포인터를 더달아서 복잡해진 대신, 원하는곳에 따로 데이터를 삽입할 수 있는 구조가 되었다