연결리스트란?
•
각 노드가 데이터와 포인터를 가지고 연결되어 있는 방식으로 데이터를 저장하는 자료구조
배열과 비슷한데 굳이 사용하는 이유
1. 칸 자체를 삭제 가능
배열은 칸 자체를 삭제할 수 없음
연결리스트는 노드 자체를 제거 가능
2. 원하는 형태로 리스트를 구현할 수 있으며, 다양하게 활용 가능
위에서 본 연결 리스트들은 모두 단일 연결 리스트(Singly Linked List)입니다. 단순히 한 노드가 다음 노드를 연결하는, 단방향 형태의 연결 리스트라고 할 수 있습니다. 여기서 더 나아가 다양한 형태로 구현할 수도 있습니다.
맨 앞과 맨 뒤가 연결되어 있는 원형 연결 리스트, 포인터가 다음 칸과 이전 칸의 주소값도 저장하는 양방향 연결 리스트, 트리형 연결 리스트 등 다양한 구조로 응용할 수 있습니다.
원리
노드
각 노드는 데이터와 다음 주소값을 저장하는 포인터로 구성되어있습니다. 따라서 구조체를 통해 구현을 합니다.
struct node
{
int data; // 변수 : 데이터 저장 공간
struct node *next; // 포인터 : 다음 노드의 주소 저장
}
typedef struct node Node; // 이렇게 하면 (struct node) -> Node로 간단하게 이름을 사용 가능
C
복사
구조체를 안 사용한다면요?구조체를 이렇게도 많이 선언합니다(with 타입 별명)
노드 사용
정적 연결리스트
#include <stdio.h>
struct node
{
int data;
struct node *next;
}
typedef struct node Node;
int main()
{
Node a, b, c, d;
a.data = 1;
a.next = &b;
b.data = 2;
b.next = &c;
c.data = 3;
c.next = &d;
d.data = 4;
d.next = NULL;
return 0;
}
C
복사
윗 코드는 사실 정적으로 구현된 연결리스트입니다. 기본적으로 위와 같은 원리 및 구조로 연결리스트가 구현되기는 하지만, 노드를 런타임에 동적으로 원하는 만큼 생성하고 삭제할 수 있어야 연결리스트로서 장점을 갖기 때문에 동적으로 구현되어야합니다.
구현
그럼 이제 컴파일 타임에 크기가 결정되는 연결리스트가 아닌, 런타임에 동적으로 노드를 생성하고 삭제할 수 있도록 구현해보겠습니다. 여기서 구현하는 연결리스트는 단일 연결리스트(Singly Linked List)입니다.
초기화
#include <stdio.h>
#include <stdlib.h>
// 노드 구조체 정의
typedef struct Node {
int data;
struct Node* next;
} Node;
// 리스트의 헤드 포인터(전역변수)
Node* head = NULL;
C
복사
노드 생성
Node* createNode(int data)
{
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
newNode->next = NULL;
return newNode;
}
C
복사
값 검색
int search(int data)
{
Node* current = head;
while (current != NULL)
{
if (current->data == data)
{
return 1;
}
current = current->next;
}
return 0;
}
C
복사
메모리 해제
void freeList()
{
Node* current = head;
while (current != NULL)
{
Node* next = current->next;
free(current);
current = next;
}
head = NULL;
}
C
복사
리스트 출력
void printList()
{
Node* current = head;
while (current != NULL)
{
printf("%d -> ", current->data);
current = current->next;
}
print("NULL\n");
}
C
복사
삽입
void insertFront(int data)
{
Node* newNode = createNode(data);
newNode->next = head;
head = newNode;
}
C
복사
void insertEnd(int data)
{
Node* newNode = createNode(data);
if (head == NULL)
{
head = newNode;
return;
}
Node* current = head;
while (current->next != NULL)
{
current = current->next;
}
current->next = newNode;
}
C
복사
삭제
void deleteNode(int data)
{
Node* current = head; // 지울 노드
Node* prev = NULL; // 지울 노드의 이전 노드
// current가 마지막 노드가 아니고 현재 데이터가 지우고 싶은 값이 아니라면, 계속 다음으로 넘어가기
while (current != NULL && current->data != data)
{
prev = current;
current = current->next;
}
// 만약 while문 이후에 current가 NULL이라면, 지우고자 하는 데이터가 없다는 뜻
if (current == NULL)
{
printf("값 %d를 찾을 수 없습니다.\n", data);
return;
}
if (prev == NULL)
{
// prev가 NULL이라는건, 삭제할 노드가 첫번째 노드인 경우 : 즉, 한 번도 이동한 적 없음
head = current->next;
}
else
{
// 삭제할 노드가 중간이나 끝에 있는 경우 : 이전 노드의 next가 current의 다음 노드를 가리키도록 변경
prev->next = current->next;
}
free(current); // 메모리 해제!
}
C
복사
사용예시
int main() {
insertEnd(10);
insertEnd(20);
insertFront(5);
insertEnd(30);
printList(); // 5 -> 10 -> 20 -> 30 -> NULL
deleteNode(20);
printList(); // 5 -> 10 -> 30 -> NULL
if (search(10)) {
printf("10을 찾았습니다!\n");
} else {
printf("10이 리스트에 없습니다.\n");
}
freeList(); // 메모리 정리
return 0;
}
C
복사
참고 자료
