연결리스트(Linked List)란?
-연결리스트(Linked List)는 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료구조이다.
- 각 노드는 다음 노드를 가리키는 포인터를 포함한다.
- 다음 노드를 가리키는 포인터는 다음 노드의 주소를 값으로 가지고 있다.
- 각 노드의 포인터 변수는 다음 노드의 데이터의 주소를 값으로 가진다. 또한 각 포인터 변수의 주소도 따로 존재한다.
(그림에 나타난 주소는 정확하지 않다. 이해를 돕기 위해 임의로 설정했다. 실제 주소값은 저런식으로 저장되지 않는다)
단순연결리스트(Singly Linked List)의 구현
가장 간단한 연결리스트인 단순 연결리스트를 구현해보자. 여러 구현 방법이 있지만, 아래 내용들을 응용하면 다양한 연결리스트를 구현할 수 있을 것이다.
노드의 구성
typedef struct _Node{
int data; /* 저장할 데이터 */
struct _Node* next; /* 다음 노드를 가리킬 포인터*/
}Node;각 노드는 저장할 데이터와 다음 노드를 가리킬 포인터로 이루어진다.
연결리스트의 초기화(init)
가장 첫번째 노드를 가리킬 포인터 Node* head 를 전역변수로 선언하고 init() 함수를 통해 초기화한다.
Node* head;
void init(){
head = NULL;
}연결리스트의 삽입(insert)
연결리스트에 노드를 삽입하는 방법을 구현해보자.
1. 가장 앞에 노드를 삽입하는 경우
1) 연결리스트가 비어 있는 경우
첫번째 노드로 정수 100을 데이터로 갖는 노드를 추가한다고 하자. 이 경우 간단하게 newNode를 만든 후 head가 newNode를 가리키도록 하면 된다.
연결리스트가 비어있는 것은 어떻게 확인할 수 있을까? head == NULL 이라면 연결리스트가 비어있는 것이다.
2) 연결리스트가 비어 있지 않은 경우
newNode를 생성 한 후 head가 가리키는 노드를 newNode의 next 포인터가 가리키게 한다.
이후 head 가 newNode를 가리키게 하면 끝이다.
2. 가장 뒤에 노드를 삽입하는 경우
마지막 노드로 정수 300을 데이터로 갖는 노드를 추가한다고 하자. 이 경우 newNode를 만든 후 마지막 노드의 next 포인터가 newNode를 가리키게 하면 될 것이다.
3. 중간에 노드를 삽입하는 경우
연결리스트 중간에 정수 200을 데이터로 갖는 노드를 추가한다고 하자. 이 경우 아래와 같은 과정을 거치면 된다.
1) 가장 먼저 newNode를 생성한다.
2) newNode의 next 포인터가 이전 노드의 next가 가리키는 노드를 가리키도록 한다.
3) 마지막으로 이전 노드의 next 포인터가 newNode를 가리키도록 하면 된다.
소스코드
모든 경우의 수를 전부 실행해보기 위해 연결리스트의 노드가 data를 기준으로 오름차순으로 저장된다고 하자.
void insert(int data){
Node* ptr;
Node* newNode = (Node*)malloc(sizeof(Node)); // newNode 할당
newNode->data = data; // 데이터 할당
newNode->next = NULL; // next 포인터 초기화
if(head == NULL){ // empty
head = newNode;
}else{
if(head->data > newNode->data){ // not empty, 가장 앞에 노드 추가
newNode->next = head;
head = newNode;
return;
}
for(ptr = head; ptr->next; ptr=ptr->next){ // 중간에 노드 추가
if(ptr->data < newNode->data && ptr->next->data > newNode->data){
newNode->next = ptr->next;
ptr->next = newNode;
return;
}
}
ptr->next = newNode; // 마지막에 노드 추가
}
}
연결리스트의 삭제(delete)
사용자가 data를 입력하면 해당 data를 갖는 노드를 연결리스트에서 삭제한다고 하자.
1. 가장 앞의 노드를 삭제하는 경우
예를 들어, 100 을 데이터로 갖는 노드를 삭제한다면, 다음과 같은 과정을 거치게 된다.
head 가 cur->next를 가리키게 하고, cur->next를 NULL 로 설정한다.
이후 cur 을 free 시키면 완료다.
2. 가장 뒤의 노드를 삭제하는 경우 & 중간 노드를 삭제하는 경우
이 경우에는, prev 라는 포인터를 이용해 삭제할 노드의 이전 노드를 가리켜야 한다.
초기에 prev 포인터와 cur 포인터는 모두 head가 가리키는 첫번째 노드를 가리킨다.
이후 cur 포인터가 다음 노드를 가리키고, 이때 사용자가 입력한 데이터 200과 cur->data 가 일치하므로 삭제 과정을 진행한다.
prev->next 가 cur->next를 가리키게 하고, 이후 cur->next 는 NULL을 가리키게 하면 된다.
이후 cur 을 free 해주면 삭제가 완료된다.
소스코드
int deleteNode(int data){
Node *cur, *prev;
cur = prev = head;
if(head == NULL){ // empty list
printf("error: list is empty!\n");
return -1;
}
if(head->data == data){ // 가장 앞의 노드 삭제
head = cur->next;
cur->next = NULL;
free(cur);
return 1;
}
for(; cur; cur= cur->next){ // 중간 혹은 마지막 노드 삭제
if(cur->data == data){
prev->next = cur->next;
cur->next = NULL;
free(cur);
return 1;
}
prev = cur;
}
printf("error : there is no %d!\n", data);
return -1; // 해당 데이터가 리스트에 존재하지 않음
}
연결리스트의 탐색(search)
사용자가 입력한 데이터가 리스트에 존재하는 지 확인하는 함수를 작성해보자.
이는 아래와 같이 간단하게 확인 가능하다.
int search_list(int data){
Node* ptr;
for(ptr = head ; ptr ; ptr=ptr->next){
if(ptr->data == data){ // data 발견
return 1;
}
}
return -1; // 데이터 미 발견
}
전체 소스코드
#include <stdio.h>
#include <stdlib.h>
typedef struct _Node{
int data; /* 저장할 데이터 */
struct _Node* next; /* 다음 노드를 가리킬 포인터*/
}Node;
Node* head;
void init(){
head = NULL;
}
void insert(int data){
Node* ptr;
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = data; // 데이터 할당
newNode->next = NULL; // next 포인터 초기화
if(head == NULL){ // empty
head = newNode;
}else{
// not empty, 가장 앞에 노드 추가
if(head->data > newNode->data){
newNode->next = head;
head = newNode;
return;
}
// 중간에 노드 추가
for(ptr = head; ptr->next; ptr=ptr->next){
if(ptr->data < newNode->data && ptr->next->data > newNode->data){
newNode->next = ptr->next;
ptr->next = newNode;
return;
}
}
ptr->next = newNode; // 마지막에 노드 추가
}
}
int deleteNode(int data){
Node *cur, *prev;
cur = prev = head;
if(head == NULL){ // empty list
printf("error: list is empty!\n");
return -1;
}
if(head->data == data){ // 가장 앞의 노드 삭
head = cur->next;
cur->next = NULL;
free(cur);
return 1;
}
for(; cur; cur= cur->next){ // 중간 혹은 마지막 노드 삭제
if(cur->data == data){
prev->next = cur->next;
cur->next = NULL;
free(cur);
return 1;
}
prev = cur;
}
printf("error : there is no %d!\n", data);
return -1; // 해당 데이터가 리스트에 존재하지 않음
}
int search_list(int data){
Node* ptr;
for(ptr = head ; ptr ; ptr=ptr->next){
if(ptr->data == data){ // data 발견
return 1;
}
}
return -1; // 데이터 미 발견
}
void printList(){
Node* ptr;
for(ptr=head; ptr->next; ptr= ptr->next){
printf("%d->", ptr->data);
}
printf("%d\n", ptr->data);
}
int main(){
int data;
init();
insert(100);
insert(300);
insert(50);
insert(200);
printList();
deleteNode(50);
printList();
deleteNode(200);
printList();
return 0;
}실행결과
'Computer Science > [자료구조]' 카테고리의 다른 글
| [자료구조] 트리의 순회, 중위 순회, 전위 순회, 후위 순회 | C언어 트리 순회 구현 (4) | 2021.07.19 |
|---|---|
| [자료구조] 트리(Tree)의 개념, 이진 트리, 전 이진 트리, 완전 이진트리, 포화 이진 트리, 이진 탐색트리 (6) | 2021.07.16 |
| [자료구조] 큐(Queue)란? | c언어 큐 구현 (3) | 2021.07.15 |
| [자료구조] 스택(stack) 의 개념과 이해 | c언어 스택 구현 (0) | 2021.07.14 |
| [자료구조] 배열(Array) 연결리스트(Linked List) 비교 (0) | 2021.07.14 |