이중연결 리스트는 앞으로도 갈 수 있고, 뒤로도 갈 수 있는 자료구조이다.
이중연결 리스트의 핵심은 이전 노드와 다음 노드가 서로 연결되어있다는 점이다.
단일 연결 리스트와 달리, 이중 연결 리스트는 각 노드가 이전 노드를 가리키는 prev, 다음 노드를 가리키는 next 포인터 두개로 구성되어 있어 앞쪽과 뒤쪽 모두로 순회할 수 있다. 이러한 양방향 순회 기능은 리스트 내에서 삽입, 삭제, 탐색 작업을 효율적으로 수행할 수 있게 해준다.
배열에서 첫 번째 원소는 항상 0번째 인덱스이다. 하지만 연결 리스트에서는 첫 번째 원소가 어디에 있는지 표시하기 위해 `head`라는 포인터를 사용해서 첫 번째 노드를 가리키고, 리스트가 비어 있을 경우 `head`는 NULL을 가리킨다.그리고 끝을 표시하는 `tail` 포인터를 사용해서 마지막 노드를 가리키고, 리스트가 비어 있으면 마찬가지로 `NULL`로 설정된다. 여기서 각 노드는 다음 노드의 주소를 저장하고 있으므로, 첫 번째 노드부터 차례대로 중간 노드에 접근할 수 있다. 이를 통해 연결 리스트에서는 첫 번째 노드, 마지막 노드, 중간 노드를 모두 관리할 수 있게 된다.
이중 연결 리스트의 장단점
장점
- 양방향 순회가 가능하다. 예를 들어, 애플리케이션에서 '되돌리기(Undo)' 기능을 구현할 때 유용하다.
- 동적으로 크기를 조절할 수 있어 연속된 메모리 할당 없이 리스트가 필요에 따라 늘어나거나 줄어들 수 있다.
- 단일 연결 리스트에 비해 연산이 더 효율적이다. 즉 노드를 탐색할 때 리스트의 시작부터 순회를 해야하는 단일 연결 리스트와 달리, 필요한 노드에 바로 접근할 수 있으니까 O(1)의 시간 복잡도로 노드를 삭제할 수 있다.
단점
- 단일 연결 리스트에 비해 각 노드가 이전 포인터를 저장해야 하므로 추가적인 메모리 오버헤드가 발생한다.
- 양방향 포인터를 관리해야 하기 때문에 단일 연결 리스트보다 구현과 관리가 복잡해서 버그 가능성이 증가한다.
- 이중 연결 리스트는 양 끝에서의 삽입과 삭제가 효율적이지만, 리스트 중간에서의 연산은 포인터 조작이 추가적으로 필요하여 복잡성이 증가한다.
- 비록 양방향 순회가 가능하지만, 리스트 전체를 순회하려면 여전히 각 노드를 하나씩 방문해야 하므로 O(n)의 시간 복잡도를 가진다.
요약하자면, 이중 연결 리스트는 단일 연결 리스트보다 더 많은 기능과 유연성을 제공하지만, 그만큼 메모리 오버헤드와 구현 복잡성도 증가한다. 특정 프로그래밍 상황에서 이중 연결 리스트를 사용할지 여부는 이러한 장단점을 이해하고 결정하는 것이 중요하다.
이중 연결 리스트 구조
이중 연결 리스트(Doubly Linked List)에서 각 노드는 세 가지 구성 요소를 포함한다.
- 데이터: 이 필드는 노드와 연관된 실제 데이터나 값을 저장한다.
- 이전 포인터: 이 포인터/참조는 리스트에서 이전 노드를 가리킨다. 이를 통해 현재 노드에서 그 이전 노드로 이동하는 양방향 순회가 가능해진다.
- 다음 포인터: 이 포인터/참조는 리스트에서 다음 노드를 가리킨다. 이전 포인터와 마찬가지로, 이를 통해 현재 노드에서 다음 노드로 이동하는 양방향 순회가 가능해진다.
아래는 노드의 기본적인 구성 요소를 보여주는 예시 코드이다.
typedef struct doublyNode
{
int value; //데이터
struct doublyNode* prev; // 이전 노드
struct doublyNode* next; // 다음 노드
}DNode;
DNode* head = NULL;
이중 연결 리스트 연산
노드 삽입하기(Insertion)
1. 리스트 앞에 삽입 (Insertion at the Beginning)
- 주어진 데이터를 가진 새로운 노드를 생성한다.
- 새로운 노드의 next 포인터를 현재 리스트의 헤드(head)를 가리키도록 설정한다.
- 리스트가 비어 있지 않다면, 현재 헤드의 prev 포인터를 새 노드를 가리키도록 업데이트한다.
- 리스트의 헤드를 새 노드를 가리키도록 업데이트한다.
2. 리스트의 끝에 삽입(Insertion at the End)
- 주어진 데이터를 가진 새로운 노드를 생성한다.
- 리스트를 순회하여 마지막 노드를 찾는다.
- 마지막 노드의 next 포인터를 새 노드를 가리키도록 설정한다.
- 새 노드의 prev 포인터를 마지막 노드를 가리키도록 설정한다.
3. 특정 위치(중간)에 삽입 (Insertion at a Specific Position (Middle))
- 주어진 데이터를 가진 새로운 노드를 생성한다.
- 원하는 위치의 노드를 찾기 위해 리스트를 순회한다.
- 해당 위치의 이전 및 이후 노드의 next와 prev 포인터를 적절히 조정하여 새 노드를 연결한다.
다음은 이중 연결 리스트에서의 노드 삽입 연산을 C 언어로 작성한 코드이다. 해당 코드는 리스트의 시작, 끝, 그리고 특정 위치에 노드를 삽입하는 작업을 수행한다.
#include <stdio.h>
#include <stdlib.h>
// 이중 연결 리스트의 노드 구조체 정의
typedef struct Node {
int data;
struct Node* prev;
struct Node* next;
} Node;
// 리스트의 헤드를 가리킬 포인터
Node* head = NULL;
// 리스트의 시작에 노드를 삽입하는 함수
void insertAtBeginning(int data) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
newNode->next = head;
newNode->prev = NULL;
if (head != NULL) {
head->prev = newNode;
}
head = newNode;
}
// 리스트의 끝에 노드를 삽입하는 함수
void insertAtEnd(int data) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
newNode->next = NULL;
newNode->prev = NULL;
// 리스트가 비어있는 경우
if (head == NULL) {
head = newNode;
return;
}
// 마지막 노드를 찾는다
Node* last = head;
while (last->next != NULL) {
last = last->next;
}
// 마지막 노드에 새로운 노드를 연결
last->next = newNode;
newNode->prev = last;
}
// 리스트의 특정 위치에 노드를 삽입하는 함수
void insertAtPosition(int data, int position) {
// 위치가 유효한지 검사
if (position < 0) {
printf("Invalid position\n");
return;
}
// 리스트의 시작에 삽입하는 경우
if (position == 0) {
insertAtBeginning(data);
return;
}
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
newNode->next = NULL;
newNode->prev = NULL;
Node* current = head;
int currentPosition = 0;
// 삽입할 위치 직전까지 이동
while (current != NULL && currentPosition < position - 1) {
current = current->next;
currentPosition++;
}
// 위치가 유효하지 않으면 삽입하지 않음
if (current == NULL) {
printf("Invalid position\n");
return;
}
// 새로운 노드를 리스트에 삽입
newNode->next = current->next;
if (current->next != NULL) {
current->next->prev = newNode;
}
current->next = newNode;
newNode->prev = current;
}
// 리스트의 노드들을 출력하는 함수
void printList() {
Node* temp = head;
while (temp != NULL) {
printf("%d ", temp->data);
temp = temp->next;
}
printf("\n");
}
int main() {
insertAtBeginning(10);
insertAtEnd(20);
insertAtEnd(30);
insertAtPosition(15, 1); // 인덱스 1 위치에 15 삽입
printList(); // 출력: 10 15 20 30
return 0;
}
특정한 값을 찾기 위해 노드 탐색하기 (Searching)
이중 연결 리스트에서의 검색(Search) 작업은 특정 요소를 찾기 위해 리스트의 시작 또는 끝에서부터 순회하면서 이루어진다. 검색 작업의 전형적인 구현 방식은 다음과 같다.
1. 리스트의 시작에서 검색 (Search from the Beginning)
- head 노드부터 리스트 순회를 시작한다.
- 각 노드의 데이터를 목표 요소와 비교한다.
- 목표 요소가 포함된 노드를 찾으면, 해당 노드 또는 그 위치를 반환한다.
- 리스트의 끝에 도달할 때까지 목표 요소를 찾지 못한 경우, null 또는 -1을 반환하여 목표 요소가 없음을 나타낸다.
아래는 C 언어로 작성된, 이중 연결 리스트에서 리스트의 시작부터 목표 요소를 검색하는 간단한 예제 코드이다.
#include <stdio.h>
#include <stdlib.h>
// 이중 연결 리스트의 노드 구조체 정의
typedef struct Node {
int data;
struct Node* prev;
struct Node* next;
} Node;
// 리스트의 헤드를 가리킬 포인터
Node* head = NULL;
// 리스트의 시작부터 목표 요소를 검색하는 함수
Node* searchFromBeginning(int target) {
Node* current = head;
// 리스트 순회하며 검색
while (current != NULL) {
if (current->data == target) {
return current; // 목표 요소를 찾으면 노드 반환
}
current = current->next; // 다음 노드로 이동
}
return NULL; // 목표 요소가 없으면 NULL 반환
}
// 리스트에 노드를 끝에 삽입하는 함수
void insertAtEnd(int data) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
newNode->next = NULL;
newNode->prev = NULL;
if (head == NULL) {
head = newNode;
return;
}
Node* last = head;
while (last->next != NULL) {
last = last->next;
}
last->next = newNode;
newNode->prev = last;
}
// 리스트의 모든 노드를 출력하는 함수 (테스트용)
void printList() {
Node* temp = head;
while (temp != NULL) {
printf("%d ", temp->data);
temp = temp->next;
}
printf("\n");
}
int main() {
// 리스트에 몇 개의 노드를 삽입
insertAtEnd(10);
insertAtEnd(20);
insertAtEnd(30);
insertAtEnd(40);
// 리스트 출력
printList(); // 출력: 10 20 30 40
// 리스트에서 20을 검색
Node* foundNode = searchFromBeginning(20);
if (foundNode != NULL) {
printf("Element found: %d\n", foundNode->data); // 출력: Element found: 20
} else {
printf("Element not found\n");
}
// 리스트에서 50을 검색 (존재하지 않는 요소)
foundNode = searchFromBeginning(50);
if (foundNode != NULL) {
printf("Element found: %d\n", foundNode->data);
} else {
printf("Element not found\n"); // 출력: Element not found
}
return 0;
}10 20 30 40
Element found: 20
Element not found- searchFromBeginning : 리스트의 시작(head)부터 순회하면서 각 노드의 data 값을 목표 요소(target)와 비교한다. 목표 요소를 찾으면 그 노드의 주소를 반환하고, 끝까지 찾지 못하면 NULL을 반환한다.
- insertAtEnd: 리스트 끝에 새로운 노드를 삽입하는 함수이다. 이를 통해 몇 개의 데이터를 리스트에 추가할 수 있다.
- printList: 리스트의 모든 노드를 순회하며 데이터를 출력하는 함수이다. 리스트가 제대로 구성되었는지 확인할 수 있다.
- main: 리스트에 10, 20, 30, 40을 삽입한 후, 리스트에서 20을 검색하고 찾았을 때와, 50처럼 없는 요소를 검색했을 때를 처리한다.
2. 리스트의 끝에서 검색 (Search from the End)
- 리스트의 마지막 노드부터 순회를 시작한다.
- 각 노드의 데이터를 목표 요소와 비교한다.
- 목표 요소가 포함된 노드를 찾으면, 해당 노드 또는 그 위치를 반환한다.
- 리스트의 시작까지 순회해도 목표 요소를 찾지 못한 경우, null 또는 -1을 반환하여 목표 요소가 없음을 나타낸다.
다음은 이중 연결 리스트에서 리스트의 끝에서부터 목표 요소를 검색하는 예제 코드이다.
#include <stdio.h>
#include <stdlib.h>
// 이중 연결 리스트의 노드 구조체 정의
typedef struct Node {
int data;
struct Node* prev;
struct Node* next;
} Node;
// 리스트의 헤드를 가리킬 포인터
Node* head = NULL;
// 리스트의 끝에서 목표 요소를 검색하는 함수
Node* searchFromEnd(int target) {
// 리스트가 비어있는 경우
if (head == NULL) {
return NULL;
}
// 리스트의 끝으로 이동
Node* current = head;
while (current->next != NULL) {
current = current->next;
}
// 리스트의 끝부터 역순으로 검색
while (current != NULL) {
if (current->data == target) {
return current; // 목표 요소를 찾으면 노드 반환
}
current = current->prev; // 이전 노드로 이동
}
return NULL; // 목표 요소가 없으면 NULL 반환
}
// 리스트에 노드를 끝에 삽입하는 함수
void insertAtEnd(int data) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
newNode->next = NULL;
newNode->prev = NULL;
if (head == NULL) {
head = newNode;
return;
}
Node* last = head;
while (last->next != NULL) {
last = last->next;
}
last->next = newNode;
newNode->prev = last;
}
// 리스트의 모든 노드를 출력하는 함수 (테스트용)
void printList() {
Node* temp = head;
while (temp != NULL) {
printf("%d ", temp->data);
temp = temp->next;
}
printf("\n");
}
int main() {
// 리스트에 몇 개의 노드를 삽입
insertAtEnd(10);
insertAtEnd(20);
insertAtEnd(30);
insertAtEnd(40);
// 리스트 출력
printList(); // 출력: 10 20 30 40
// 리스트의 끝에서 20을 검색
Node* foundNode = searchFromEnd(20);
if (foundNode != NULL) {
printf("Element found: %d\n", foundNode->data); // 출력: Element found: 20
} else {
printf("Element not found\n");
}
// 리스트의 끝에서 50을 검색 (존재하지 않는 요소)
foundNode = searchFromEnd(50);
if (foundNode != NULL) {
printf("Element found: %d\n", foundNode->data);
} else {
printf("Element not found\n"); // 출력: Element not found
}
return 0;
}- searchFromEnd : 리스트의 마지막 노드부터 시작해서 목표 요소를 역순으로 검색한다. 먼저 current 포인터를 리스트의 마지막 노드로 이동시킨 후, 그 포인터를 prev 방향으로 이동하면서 목표 요소를 찾는다. 목표 요소를 찾으면 그 노드를 반환하고, 찾지 못하면 NULL을 반환한다.
- insertAtEnd : 리스트의 끝에 새로운 노드를 추가하는 함수이다. 이를 통해 리스트에 데이터를 추가할 수 있다.
- printList : 리스트에 있는 모든 노드를 순회하며 데이터를 출력하는 함수이다. 리스트가 올바르게 구성되었는지 확인할 수 있다.
- main : insertAtEnd 함수를 사용해 리스트에 10, 20, 30, 40을 삽입한 후, searchFromEnd를 사용해 리스트의 끝에서 20을 검색한다. 또한 리스트에서 존재하지 않는 요소 50을 검색하여 처리한다.
모든 노드를 한 번씩 방문하기 위해 순회하기 (Traverse)
순회(Traversal) 이중 연결 리스트에서의 순회는 각 노드를 차례대로 방문하는 작업으로, 리스트의 시작부터 끝까지 또는 끝에서 시작까지 양방향으로 진행될 수 있다. 순회는 다음과 같이 구현된다.
1.시작부터 끝까지 순회 (순방향 Traversal)
- 리스트의 head 노드에서부터 순회를 시작한다.
- 각 노드를 방문하고 원하는 작업을 수행한다 (예: 데이터를 출력).
- next 포인터를 사용하여 다음 노드로 이동한다.
- next 포인터가 null인 노드에 도달할 때까지 순회를 계속한다 (즉, 리스트의 끝에 도달할 때까지).
2.끝에서 시작까지 순회 (역방향 Traversal)
- 리스트의 마지막 노드에서부터 순회를 시작한다.
- 각 노드를 방문하고 원하는 작업을 수행한다.
- prev 포인터를 사용하여 이전 노드로 이동한다.
- prev 포인터가 null인 노드에 도달할 때까지 순회를 계속한다 (즉, 리스트의 시작에 도달할 때까지).
#include <stdio.h>
#include <stdlib.h>
// 이중 연결 리스트의 노드 구조체 정의
typedef struct Node {
int data;
struct Node* prev;
struct Node* next;
} Node;
// 리스트의 헤드를 가리킬 포인터
Node* head = NULL;
// 리스트에 노드를 끝에 삽입하는 함수
void insertAtEnd(int data) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
newNode->next = NULL;
newNode->prev = NULL;
if (head == NULL) {
head = newNode;
return;
}
Node* last = head;
while (last->next != NULL) {
last = last->next;
}
last->next = newNode;
newNode->prev = last;
}
// 리스트의 순방향 순회 (Forward Traversal)
void forwardTraversal() {
Node* current = head;
while (current != NULL) {
printf("%d ", current->data); // 현재 노드의 데이터 출력
current = current->next; // 다음 노드로 이동
}
printf("\n"); // 순회가 끝난 후 줄 바꿈
}
// 리스트의 역방향 순회 (Reverse Traversal)
void reverseTraversal() {
if (head == NULL) {
return; // 리스트가 비어있는 경우
}
Node* current = head;
// 리스트의 마지막 노드로 이동
while (current->next != NULL) {
current = current->next;
}
// 리스트의 끝에서부터 순회 시작
while (current != NULL) {
printf("%d ", current->data); // 현재 노드의 데이터 출력
current = current->prev; // 이전 노드로 이동
}
printf("\n"); // 순회가 끝난 후 줄 바꿈
}
int main() {
// 몇 개의 노드를 리스트에 추가
insertAtEnd(10);
insertAtEnd(20);
insertAtEnd(30);
insertAtEnd(40);
printf("Forward Traversal:\n");
forwardTraversal(); // 출력: 10 20 30 40
printf("Reverse Traversal:\n");
reverseTraversal(); // 출력: 40 30 20 10
return 0;
}Forward Traversal:
10 20 30 40
Reverse Traversal:
40 30 20 10- insertAtEnd : 리스트의 끝에 새로운 노드를 추가하기 위해 데이터를 입력받아 노드를 생성하고 리스트의 끝에 추가한다.
- forwardTraversal 함수: 리스트의 헤드에서 시작하여 순방향으로 순회하며 각 노드의 데이터를 출력한다. current = current->next로 현재 노드에서 다음 노드로 이동한다.
- reverseTraversal 함수: 리스트의 마지막 노드에서 시작하여 역방향으로 순회하며 각 노드의 데이터를 출력한다.리스트의 마지막 노드를 찾은 후, current = current->prev로 이전 노드로 이동하면서 데이터를 출력한다.
- main 함수: insertAtEnd 함수를 이용해 리스트에 몇 개의 노드를 추가한 뒤, 순방향과 역방향으로 순회하여 노드의 데이터를 출력한다.
노드 뒤집기(Reversal)
이중 연결 리스트(Doubly Linked List)를 반전시키려면 각 노드의 prev와 next 포인터를 교환해야 한다. 또한, head 포인터는 원래의 마지막 노드를 가리키도록, tail 포인터는 원래의 첫 번째 노드를 가리키도록 업데이트해야 한다.이 과정은 리스트의 노드를 하나씩 순회하면서 prev와 next 포인터를 서로 교환한 후, 마지막으로 head와 tail 포인터를 적절하게 수정하여 리스트를 반전시킨다.
노드 뒤집는 순서:
- 포인터 교환: 각 노드에서 prev와 next 포인터를 서로 교환한다.
- 포인터 업데이트: 리스트의 head는 원래 마지막 노드를, tail은 원래 첫 번째 노드를 가리키도록 업데이트한다.
- 제자리 반전: 별도의 리스트나 추가 메모리를 사용하지 않고, 기존 리스트의 노드를 제자리에서 반전시킨다.
#include <stdio.h>
#include <stdlib.h>
// 이중 연결 리스트의 노드 구조체 정의
typedef struct Node {
int data;
struct Node* prev;
struct Node* next;
} Node;
Node* head = NULL; // 리스트의 시작점(헤드)
Node* tail = NULL; // 리스트의 끝(꼬리)
// 리스트의 끝에 노드를 삽입하는 함수
void insertAtEnd(int data) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
newNode->next = NULL;
newNode->prev = NULL;
if (head == NULL) {
head = newNode;
tail = newNode;
return;
}
tail->next = newNode;
newNode->prev = tail;
tail = newNode;
}
// 리스트를 역순으로 뒤집는 함수
void reverse() {
if (head == NULL || head->next == NULL) {
return; // 리스트가 비어있거나 노드가 1개인 경우
}
Node* current = head;
Node* temp = NULL;
// 각 노드의 prev와 next 포인터를 교환
while (current != NULL) {
temp = current->prev;
current->prev = current->next;
current->next = temp;
current = current->prev; // 원래 방향으로 다음 노드로 이동
}
// 새로운 헤드와 테일 업데이트
if (temp != NULL) {
head = temp->prev;
tail = head;
while (tail->next != NULL) {
tail = tail->next;
}
}
}
// 리스트의 순방향 순회(출력)
void forwardTraversal() {
Node* current = head;
while (current != NULL) {
printf("%d ", current->data);
current = current->next;
}
printf("\n");
}
int main() {
// 몇 개의 노드를 리스트에 추가
insertAtEnd(10);
insertAtEnd(20);
insertAtEnd(30);
insertAtEnd(40);
printf("Before Reverse:\n");
forwardTraversal(); // 출력: 10 20 30 40
reverse(); // 리스트를 역순으로 뒤집음
printf("After Reverse:\n");
forwardTraversal(); // 출력: 40 30 20 10
return 0;
}Before Reverse:
10 20 30 40
After Reverse:
40 30 20 10- insertAtEnd 함수: 리스트의 끝에 노드를 추가하기 위해 새로 생성된 노드를 테일에 추가하고 prev와 next 포인터를 업데이트한다.
- reverse 함수: 리스트의 모든 노드의 prev와 next 포인터를 교환하여 리스트를 역순으로 뒤집는다. 마지막으로 헤드 포인터를 업데이트하여 리스트의 첫 번째 노드가 뒤집힌 후의 마지막 노드가 되도록 한다.
- forwardTraversal 함수:리스트의 모든 노드를 순차적으로 순회하며 각 노드의 데이터를 출력한다.
- main 함수: 4개의 노드를 리스트에 삽입하고, 역순으로 뒤집은 후, 역순으로 바뀐 리스트를 출력한다.
노드 삭제하기 (Deletion)
1. 리스트의 시작에서 삭제
- head 포인터를 다음 노드를 가리키도록 업데이트한다.
- 리스트가 비어 있지 않으면, 새로운 헤드의 prev 포인터를 null로 설정한다.
2. 리스트의 끝에서 삭제
- 리스트를 순회하여 마지막 노드를 찾는다.
- 마지막에서 두 번째 노드의 next 포인터를 null로 설정한다.
3. 특정 노드(중간 노드) 삭제
- 삭제할 노드를 찾기 위해 리스트를 순회한다.
- 삭제할 노드 앞뒤 노드의 next와 prev 포인터를 조정하여 삭제할 노드를 우회(bypass)한다.
C 언어로 이중 연결 리스트에서 노드 삭제를 구현한 코드이다. 이 코드에서는 리스트의 처음, 끝, 그리고 특정 위치에서 노드를 삭제한다.
#include <stdio.h>
#include <stdlib.h>
// 이중 연결 리스트의 노드 구조체 정의
typedef struct Node {
int data;
struct Node* prev;
struct Node* next;
} Node;
Node* head = NULL; // 리스트의 시작점(헤드)
Node* tail = NULL; // 리스트의 끝(테일)
// 리스트의 끝에 노드를 삽입하는 함수
void insertAtEnd(int data) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
newNode->next = NULL;
newNode->prev = NULL;
if (head == NULL) {
head = newNode;
tail = newNode;
return;
}
tail->next = newNode;
newNode->prev = tail;
tail = newNode;
}
// 리스트의 처음에서 노드를 삭제하는 함수
void deleteAtBeginning() {
if (head == NULL) {
printf("List is empty.\n");
return;
}
Node* temp = head;
head = head->next;
if (head != NULL) {
head->prev = NULL;
} else {
tail = NULL; // 리스트에 노드가 1개였을 경우, tail도 NULL로 설정
}
free(temp);
}
// 리스트의 끝에서 노드를 삭제하는 함수
void deleteAtEnd() {
if (head == NULL) {
printf("List is empty.\n");
return;
}
Node* temp = tail;
if (head == tail) {
// 노드가 1개일 때
head = NULL;
tail = NULL;
} else {
tail = tail->prev;
tail->next = NULL;
}
free(temp);
}
// 특정 위치의 노드를 삭제하는 함수
void deleteAtPosition(int position) {
if (head == NULL || position < 0) {
printf("List is empty or invalid position.\n");
return;
}
if (position == 0) {
deleteAtBeginning();
return;
}
Node* current = head;
int currentPosition = 0;
// 특정 위치까지 이동
while (current != NULL && currentPosition < position) {
current = current->next;
currentPosition++;
}
if (current == NULL) {
printf("Position out of range.\n");
return;
}
if (current->next != NULL) {
current->next->prev = current->prev;
}
if (current->prev != NULL) {
current->prev->next = current->next;
}
free(current);
}
// 리스트의 노드들을 출력하는 함수
void displayList() {
Node* current = head;
while (current != NULL) {
printf("%d ", current->data);
current = current->next;
}
printf("\n");
}
int main() {
insertAtEnd(10);
insertAtEnd(20);
insertAtEnd(30);
insertAtEnd(40);
insertAtEnd(50);
printf("Original List: ");
displayList(); // 출력: 10 20 30 40 50
// 리스트의 첫 노드 삭제
deleteAtBeginning();
printf("After deleting at the beginning: ");
displayList(); // 출력: 20 30 40 50
// 리스트의 마지막 노드 삭제
deleteAtEnd();
printf("After deleting at the end: ");
displayList(); // 출력: 20 30 40
// 특정 위치의 노드 삭제 (예: 1번 인덱스 노드 삭제)
deleteAtPosition(1);
printf("After deleting at position 1: ");
displayList(); // 출력: 20 40
return 0;
}Original List: 10 20 30 40 50
After deleting at the beginning: 20 30 40 50
After deleting at the end: 20 30 40
After deleting at position 1: 20 40
- insertAtEnd: 리스트의 끝에 노드를 삽입하기 위해 새로 생성된 노드를 테일에 추가한다.
- deleteAtBeginning: 리스트의 첫 번째 노드를 삭제하는 함수이다. 리스트의 head를 다음 노드로 옮기고, 기존의 첫 번째 노드를 삭제한다.
- deleteAtEnd: 리스트의 마지막 노드를 삭제하는 함수이다. 테일을 이전 노드로 옮기고, 기존의 마지막 노드를 삭제한다.
- deleteAtPosition: 리스트의 특정 위치에 있는 노드를 삭제하는 함수이다. 주어진 위치까지 리스트를 순회하여 해당 노드를 삭제하고, 그 이전과 이후의 노드를 연결한다.
- displayList: 리스트의 모든 노드를 순차적으로 출력한다.
노드가 1개 일 때 삭제하기
연결 리스트에 노드가 하나만 있는 경우, 리스트를 초기화하기 위해 그 노드를 제거하고, 시작을 의미하는 'head'와 끝을 의미하는 'tail'을 모두 NULL로 설정해야 한다. 여기에서 노드를 제거한다는 것은 단순히 메모리 공간 안에 있는 값을 초기화하는 것이 아니라 메모리 공간 자체를 해제하는 것을 의미한다. 즉, 해당 노드가 차지하고 있던 메모리를 반환해서 다시 사용할 수 있도록 시스템에 돌려주는 작업이다. 이 과정에서 메모리 안의 값은 중요하지 않으며, 그 값을 0으로 바꿔주지 않고 메모리 자체를 해제한다.
C 언어에서는 동적 메모리를 할당할 때 `malloc` 함수를 사용하고, 할당한 메모리를 해제할 때는 `free` 함수를 사용한다.
`free`를 통해 메모리 해제를 하면, 그 메모리 공간은 다시 다른 용도로 사용할 수 있게 된다.따라서 노드를 제거한다는 것은 동적으로 할당된 노드의 메모리를 free로 해제하는 과정이라고 이해하면 된다.
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node* next;
} Node;
void deleteNode(Node** head, Node** tail) {
if (*head == NULL) {
printf("리스트가 비어있습니다.\n");
return;
}
// 노드가 하나만 있을 때
if (*head == *tail) {
free(*head); // 메모리 해제
*head = NULL; // head 초기화
*tail = NULL; // tail 초기화
}
}
int main() {
// 노드 생성
Node* head = (Node*)malloc(sizeof(Node));
Node* tail = head;
head->data = 10;
head->next = NULL;
printf("노드 값: %d\n", head->data);
// 노드 삭제
deleteNode(&head, &tail);
if (head == NULL) {
printf("노드가 삭제되었습니다.\n");
}
return 0;
}
노드가 1개 이상일 때 맨 앞 노드를 삭제하기
이중 연결 리스트에서 노드가 1개 이상인경우, 대기룸에서 사람들이 대기자가 빠진 만큼 대기 의자를 앞으로 땡겨앉듯이, 첫 번째 노드를 제거한 뒤에 head를 그 다음 노드로 이동시킨다. head가 새로운 첫 번째 노드로 변경된 후, 새로운 첫 번째 노드의 이전 포인터(prev)가 존재한다면 이를 NULL로 설정하여 이 노드가 이제 리스트의 첫 번째 노드임을 표시해주면 된다. 이제 무쓸모가 된 첫 번째 노드를 free로 해제하여 시스템에 반환하면 맨 앞 노드를 삭제할 수 있다.
#include <stdio.h>
#include <stdlib.h>
// 이중 연결 리스트 노드 구조체 정의
typedef struct Node {
int data;
struct Node* prev;
struct Node* next;
} Node;
// 이중 연결 리스트에서 맨 앞 노드를 삭제하는 함수
void deleteFirstNode(Node** head) {
if (*head == NULL) {
printf("리스트가 비어있습니다.\n");
return;
}
Node* temp = *head; // 첫 번째 노드를 가리킴
*head = (*head)->next; // head를 두 번째 노드로 이동
if (*head != NULL) {
(*head)->prev = NULL; // 새로운 첫 번째 노드의 prev를 NULL로 설정
}
free(temp); // 이전 첫 번째 노드의 메모리 해제
}
// 이중 연결 리스트에 노드 추가 (맨 끝에 추가)
void appendNode(Node** head, int data) {
Node* newNode = (Node*)malloc(sizeof(Node));
Node* last = *head;
newNode->data = data;
newNode->next = NULL;
// 리스트가 비어 있으면 새로운 노드를 head로 설정
if (*head == NULL) {
newNode->prev = NULL;
*head = newNode;
return;
}
// 마지막 노드를 찾음
while (last->next != NULL)
last = last->next;
// 새로운 노드를 마지막 노드의 next로 연결
last->next = newNode;
newNode->prev = last;
}
// 이중 연결 리스트 출력
void printList(Node* node) {
while (node != NULL) {
printf("%d ", node->data);
node = node->next;
}
printf("\n");
}
int main() {
Node* head = NULL;
// 노드 추가
appendNode(&head, 10);
appendNode(&head, 20);
appendNode(&head, 30);
// 리스트 출력
printf("삭제 전 리스트: ");
printList(head);
// 첫 번째 노드 삭제
deleteFirstNode(&head);
// 리스트 출력
printf("첫 번째 노드 삭제 후 리스트: ");
printList(head);
// 또 한 번 첫 번째 노드 삭제
deleteFirstNode(&head);
// 리스트 출력
printf("두 번째 노드 삭제 후 리스트: ");
printList(head);
return 0;
}'자료구조&알고리즘' 카테고리의 다른 글
| 연결리스트란? (1) | 2024.12.09 |
|---|---|
| 연결리스트와 배열의 비교 (0) | 2024.12.09 |
| 알고리즘의 성능을 평가하는 빅오 표기법 (1) | 2024.10.06 |
| 단일 연결 리스트(Singly Linked List) (0) | 2024.10.05 |
| 자료구조란? (5) | 2024.10.04 |
