이중 연결 리스트(Doubly Linked List)
노드와 노드가 서로 연결되어 있으며, 단순 연결 리스트와는 달리, 이전 노드와 다음 노드에 대한 포인터를 보유한다.
장점
노드 탐색 시 단순 연결 리스트보다 효율적임.
단점
- 이전 노드를 가리키기 위한 추가 변수 사용(더 많은 메모리 사용)
- 단순 연결 리스트에 비해 구현이 복잡함
원형 연결 리스트(Circular Linked List)
- 끝이 없으며, 원형으로 순환하는 연결 리스트
- 무한 루프에 주의해야 함
원형 연결 리스트 코드 구현
#include <iostream>
using namespace std;
// 데이터 구조
typedef struct ListNode {
int data;
struct ListNode* next;
} ListNode;
int CircularListLength(ListNode* head) {
int len = 0;
ListNode* current = head;
while (current != NULL)
{
len++;
current = current->next;
}
return len;
}
// 모든 노드 출력
void PrintList(ListNode* head) {
if (head == NULL) {
cout << "NULL\n";
return;
}
ListNode* current = head;
do {
cout << current->data << " -> ";
current = current->next;
} while (current != head);
cout << "HEAD\n";
}
// 맨 앞에 노드 추가
void InsertAtBegin(ListNode * *head, int data) {
ListNode* inserted = new ListNode;
inserted->data = data;
if (*head == NULL) {
*head = inserted;
inserted->next = *head;
}
else {
ListNode* tail = *head;
while (tail->next != *head) {
tail = tail->next;
}
inserted->next = *head;
*head = inserted;
tail->next = *head;
}
}
// 맨 끝에 노드 추가
void InsertAtEnd(ListNode * *head, int data) {
ListNode* inserted = new ListNode;
inserted->data = data;
if (*head == NULL) {
*head = inserted;
inserted->next = *head;
}
else {
ListNode* tail = *head;
while (tail->next != *head) {
tail = tail->next;
}
tail->next = inserted;
inserted->next = *head;
}
}
// 맨 앞 노드 삭제
void DeleteFrontNode(ListNode * *head) {
ListNode* removed = *head;
if (*head == NULL) {
return;
}
else {
ListNode* tail = *head;
while (tail->next != *head) {
tail = tail->next;
}
if (tail == *head) {
*head = NULL;
}
else {
(*head) = (*head)->next;
tail->next = *head;
}
delete(removed);
}
}
// 맨 마지막 노드 삭제
void DeleteLastNode(ListNode * *head) {
if (*head == NULL) {
return;
}
else {
ListNode* tail = *head;
ListNode* tail_prev = NULL;
while (tail->next != *head) {
tail_prev = tail;
tail = tail->next;
}
ListNode* removed = tail;
if (tail == *head) {
*head = NULL;
}
else {
tail_prev->next = *head;
}
delete(removed);
}
}참고
Security & Develop