All
연결리스트의 변형
단순 연결리스트의 단점
•
기본 구조
각 노드는 data 필드와 link(다음 노드 주소) 필드로 구성된다.
[data | link] → [data | link] → [data | NULL]
Plain Text
복사
•
단점
◦
각 노드에서 후행 노드만 가리키므로 특정 노딍 선행 노드에 대한 접근을 헤드부터 재검색해야함
◦
마지막 노드는 항상 NULL을 가리킴
→ 이런 문제점을 보완하기 위해 원형 연결 리스트와 이중 연결 리스트 나옴
종류 | 구조적 특징 | 장점 | 단점 |
단순 연결 리스트 | 노드가 data + link 로 구성, 단방향 연결 | 구현이 간단 | 역방향 탐색 불가 |
원형 연결 리스트 | 마지막 노드의 링크가 head를 가리킴 | 리스트 전체를 반복 탐색 가능 | 끝과 처음 구분 어려움 |
이중 연결 리스트 | 각 노드가 Llink, data, Rlink 가짐 | 양방향 탐색, 삽입·삭제 용이 | 메모리 추가 소모, 포인터 관리 복잡 |
원형 연결 리스트
1. 정의 및 생성
구조체
typedef struct ListNode {
int data;
struct ListNode* link; // 다음 노드 (원형이므로 마지막 노드의 link는 head)
} listNode;
typedef struct {
listNode* head; // 공백이면 NULL
} linkedList_h;
C
복사
생성 함수
linkedList_h* createLinkedList_h(void) {
linkedList_h* H = (linkedList_h*)malloc(sizeof(linkedList_h));
H->head = NULL;
return H;
}
C
복사
•
ListNode: 원형 연결 리스트의 기본 노드 구조
•
linkedList_h: head 포인터만을 가진 헤드 노드 구조
•
createLinkedList_h(): 리스트를 동적 생성하고 head를 NULL로 초기
2. 노드 삽입
2-1. 공백 리스트일때
•
첫 노드를 삽입할 때는 head가 새 노드를 가리키고, link도 자기 자신을 가리키게 하여 원형 구조를 만든다.
if (H->head == NULL) {
H->head = NewNode;
NewNode->link = NewNode; // 자기 자신을 가리켜 원형 완성
return;
}
else: ...
C
복사
2-2. 원형 연결 리스트가 공백이 아닌 경우
else {
tempNode = H->head;
while (tempNode->link != H->head)
tempNode = tempNode->link; // 마지막 노드 탐색
NewNode->link = tempNode->link; // 새 노드의 link = head
tempNode->link = NewNode; // 마지막 노드의 link = 새 노드
H->head = NewNode; // head를 새 노드로 갱신
}
C
복사
2-3. 중간 위치 삽입
void addMiddleNode(linkedList_h* H, listNode* preNode, int itdata) {
listNode* NewNode;
NewNode = (listNode*)malloc(sizeof(listNode));
NewNode->data = itdata;
NewNode->link = NULL;
NewNode->link = preNode->link; // 새 노드가 preNode의 다음을 가리킴
preNode->link = NewNode; // preNode가 새 노드를 가리키게 수정
return;
}
C
복사
예시
초기 리스트:
head → [10] → [20] → [30] ──┐
↑ │
└─────────────────┘
Plain Text
복사
삽입: 데이터 5
포인터 흐름:
1.
tempNode는 [30]을 찾음 (마지막 노드)
2.
NewNode(5)->link = head(10)
3.
tempNode(30)->link = NewNode(5)
4.
head = NewNode(5)
결과:
head → [5] → [10] → [20] → [30]
↑ │
└────────────────────┘
Plain Text
복사
3. 노드 삭제
단일 원형 리스트에서 삭제 노드의 직전 노드(prev)를 찾아 그 prev->link 를 삭제 노드의 다음으로 바꾸는 것이 핵심이다. 삭제 대상이 head인 경우엔 head 갱신과 마지막 노드의 link 재연결이 함께 필요하다.
3-1. 삭제 대상 탐색 함수
void finddelCircularNode(linkedList_h* H, int itdata) {
listNode* tempNode;
listNode* prevNode;
if (H->head == NULL) { // 공백 리스트
printf("Circular Linked List is EMPTY\n");
return;
}
// prevNode를 '마지막 노드'로 맞춰 둠
prevNode = H->head;
while (prevNode->link != H->head)
prevNode = prevNode->link;
// 첫 노드부터 검색
tempNode = H->head;
do {
if (tempNode->data == itdata) { // 찾으면 삭제 함수 호출
deleteCircularNode(H, prevNode);
return;
} else {
prevNode = tempNode; // 선행 노드 갱신
tempNode = tempNode->link; // 다음 노드로
}
} while (tempNode != H->head);
// 한 바퀴 돌고도 못 찾음
printf("Search Fail\n");
return;
}
C
복사
•
공백이면 즉시 종료 메시지
•
prevNode를 마지막 노드로 맞춰 두고 시작하면, 첫 노드(head)가 곧바로 삭제 대상이어도 prevNode가 올바른 선행 노드가 됨
•
do–while로 한 바퀴 정확히 돌고, 못 찾으면 Search Fail
동작 예시
•
리스트: head → [10] → [20] → [30] → head
•
삭제 탐색값: 10
시작 시 prevNode=마지막(30), tempNode=head(10) → 바로 매치 → deleteCircularNode(H, prevNode) 호출 → head 삭제 정상 처리
3-2. 실제 삭제 함수
•
delNode = prevNode->link (삭제 대상은 선행 노드의 다음)
•
단일 노드: 자기 자신만 가리키면 head=NULL 후 free
•
일반: prevNode->link = delNode->link, 필요하면 head 갱신
void deleteCircularNode(linkedList_h* H, listNode* prevNode) {
listNode* delNode;
if (H->head == NULL) return; // 안전장치
delNode = prevNode->link; // 삭제 대상 노드
// (1) 노드가 1개뿐인 경우
if (delNode == H->head && delNode->link == H->head) {
H->head = NULL;
free(delNode);
return;
}
// (2) 일반 경우 (선행 → 대상 → 다음)
prevNode->link = delNode->link; // 대상 건너뛰어 연결
if (delNode == H->head) // 대상이 head라면 head 이동
H->head = delNode->link;
free(delNode);
return;
}
C
복사
포인터 흐름 예시 1 — head(10) 삭제
초기: head → 10 → 20 → 30 → head
•
prevNode=30, delNode=10
•
prevNode->link = 20, head = 20, free(10)
결과: head → 20 → 30 → head
포인터 흐름 예시 2 — 중간(30) 삭제
초기: head → 10 → 20 → 30 → 40 → head
•
탐색 중 prevNode=20, delNode=30
•
prevNode->link = 40, head 변화 없음, free(30)
결과: head → 10 → 20 → 40 → head
이중 연결 리스트
1. 정의 및 생성
구조체 정의
typedef struct ListNode {
struct ListNode* Llink; // 왼쪽(이전 노드)
int data; // 데이터 필드
struct ListNode* Rlink; // 오른쪽(다음 노드)
} listNode;
typedef struct {
listNode* Lhead; // 리스트의 첫 노드를 가리킴
listNode* Fhead; // 리스트의 마지막 노드를 가리킴
} linkedList_h;
C
복사
리스트 생성 함수
linkedList_h* createLinkedList_h(void) {
linkedList_h* H;
H = (linkedList_h*)malloc(sizeof(linkedList_h));
H->Lhead = NULL; // 첫 노드
H->Fhead = NULL; // 마지막 노드
return H;
}
C
복사
생성 결과
H ─→ [Lhead | NULL]
[Fhead | NULL]
Plain Text
복사
→ 아직 노드가 없으므로 양쪽 포인터 모두 NULL
2. 노드 삽입
이중 연결 리스트는 양방향 포인터 조정이 핵심
void insertDNode(linkedList_h* H, listNode* prevNode, int item) {
listNode* NewNode;
NewNode = (listNode*)malloc(sizeof(listNode));
NewNode->data = item;
NewNode->Llink = NULL;
NewNode->Rlink = NULL;
// 리스트가 공백이면 첫 노드 삽입
if (H->Lhead == NULL) {
H->Lhead = NewNode;
H->Fhead = NewNode;
return;
}
// 일반 삽입 (prevNode 뒤)
NewNode->Rlink = prevNode->Rlink; // 새 노드 오른쪽을 prevNode의 오른쪽으로
if (prevNode->Rlink != NULL)
prevNode->Rlink->Llink = NewNode; // 기존 다음 노드가 있다면 왼쪽 연결 수정
prevNode->Rlink = NewNode; // prevNode 오른쪽 → 새 노드
NewNode->Llink = prevNode; // 새 노드 왼쪽 → prevNode
// 만약 prevNode가 마지막 노드라면 Fhead 갱신
if (prevNode == H->Fhead)
H->Fhead = NewNode;
}
C
복사
예시
초기:
[Lhead] → [100] ↔ [200] ↔ [300] ← [Fhead]
Plain Text
복사
삽입: prevNode = [200], item = 250
포인터 변화:
1.
NewNode(250)->Rlink = prevNode(200)->Rlink(300)
2.
prevNode(200)->Rlink = NewNode(250)
3.
NewNode(250)->Llink = prevNode(200)
4.
nextNode(300)->Llink = NewNode(250)
결과:
[Lhead] → [100] ↔ [200] ↔ [250] ↔ [300] ← [Fhead]
Plain Text
복사
3. 노드 삭제
void deleteDNode(linkedList_h* H, listNode* delNode) {
delNode->Llink->Rlink = delNode->Rlink;
delNode->Rlink->Llink = delNode->Llink;
free(delNode);
}
C
복사
포인터 흐름
1.
delNode->Llink->Rlink = delNode->Rlink
→ 왼쪽 노드의 오른쪽 포인터가 삭제 노드의 오른쪽 노드를 가리킴
2.
delNode->Rlink->Llink = delNode->Llink
→ 오른쪽 노드의 왼쪽 포인터가 삭제 노드의 왼쪽 노드를 가리킴
3.
free(delNode)
→ 삭제 노드 메모리 해제
예시
초기:
[Lhead] → [100] ↔ [200] ↔ [300] ↔ [400] ← [Fhead]
Plain Text
복사
삭제: delNode = [300]
포인터 조정:
[200].Rlink = [400]
[400].Llink = [200]
free([300])
Plain Text
복사
결과:
[Lhead] → [100] ↔ [200] ↔ [400] ← [Fhead]
Plain Text
복사