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;
}
느낀점 ; 앞에 포인터를 더달아서 복잡해진 대신, 원하는곳에 따로 데이터를 삽입할 수 있는 구조가 되었다
'이론공부 > 자료구조' 카테고리의 다른 글
자료구조 공부 #17 (트리순회) (0) | 2021.05.16 |
---|---|
자료구조 공부 #16 (트리) (0) | 2021.05.04 |
자료구조 공부#14 (연결리스트2) (0) | 2021.04.20 |
자료구조 공부#13 (연결리스트) (0) | 2021.04.13 |
자료구조 공부#12 (덱) (0) | 2021.04.09 |