Taking baby-developer steps
2-1. 연결 리스트 - 필요성 / 배열 기반 리스트 / 배열 기반 리스트의 특징 / 연결 리스트(단일 연결리스트)/ 연결 리스트 구조체 만들기 / 연결 리스트 삽입 함수 / 연결 리스트 삭제 함수 본문
2-1. 연결 리스트 - 필요성 / 배열 기반 리스트 / 배열 기반 리스트의 특징 / 연결 리스트(단일 연결리스트)/ 연결 리스트 구조체 만들기 / 연결 리스트 삽입 함수 / 연결 리스트 삭제 함수
Surin Lee 2021. 4. 5. 01:21연결리스트
연결리스트의 필요성과 쓰임새에 대해 학습한다. C언어를 활용하여 연결 리스트를 구현하는 방법에 대해서 공부한다.
연결 리스트는 데이터를 선형적으로 저장하고 처리하는 한 방법이다. 기존에 배열을 이용했을 때보다 삽입과 삭제가 많은 경우에서 효율적이다. 다만 특정한 인덱스에 바로 참조해야 할 때가 많다면 배열을 이용하는 것이 효율적이다.
연결리스트의 필요성
일반적으로 배열을 사용하여 데이터를 순차적으로 저장하고, 나열할 수 있다. 배열을 사용하는 경우, 메모리 공간이 불필요하게 낭비 될 수 있다.
배열 기반의 리스트
데이터를 순차적으로 저장하고, 처리할 때는 배열 기반의 리스트를 다음과 같이 간단히 이용 할 수 있다.
#include<stdio.h>
#define INF 10000
int arr[INF];
int count = 0;
void addBack(int data){
arr[count] = data;
count++;
}
void addFirst(int data){
for(int i = count; i>=1; i--){
arr[i] = arr[i-1];
}
arr[0] = data;
count++;
}
void show(){
for(int i=0; i<count; i++){
printf("%d ", arr[i]);
}
}
int main(void){
addFirst(4);
addFirst(5);
addFirst(1);
addBack(7);
addBack(6);
addBack(8);
show();
system("pause");
return 0;
}1 5 4 7 6 8배열기반 리스트를 위와 같이 특정한 data를 배열의 뒷부분에 담는 함수 addBack(), 가장 앞 부분에 원소를 담는 addFirst(), 배열에 담겨있는 모든 원소를 출력하는 show()함수를 정의하여 사용 할 수 있다.
이 경우, 특정한 위치의 원소를 삭제하는 함수(removeAt())는 다음과 같이 정의 할 수 있다.(show 함수 일부 수정)
#include<stdio.h>
#define INF 10000
int arr[INF];
int count = 0;
void addBack(int data){
arr[count] = data;
count++;
}
void addFirst(int data){
for(int i = count; i>=1; i--){
arr[i] = arr[i-1];
}
arr[0] = data;
count++;
}
void removeAt(int index){
for(int i = index; i<count; i++){
arr[i]=arr[i+1];
}
count--;
}
void show(){
for(int i=0; i<count; i++){
printf("%d ", arr[i]);
}
printf("\n");
}
int main(void){
addFirst(4);
addFirst(5);
addFirst(1);
addBack(7);
addBack(6);
addBack(8);
show();
removeAt(4);
show();
system("pause");
return 0;
}1 5 4 7 6 8
1 5 4 7 8특정한 위치의 원소를 삭제하는 removeAt()함수을 정의할 때의 핵심은, show()함수가 i<count 일때까지 해당 인덱스의 원소를 출력하므로, count를 줄여서 맨 뒤의 원소를 출력되지 않게 하는데에 있다.
배열 기반 리스트의 특징
배열로 만들었으므로, 특정한 위치의 원소에 index를 활용해 즉시 접근할 수 있다는 장점이 있다. 데이터가 들어갈 공간을 미리 메모리에 할당해야 한다는 단점이 있다. 원하는 위치로의 삽입이나 삭제가 비효율적이다. 이를 다른 말로 하면, "배열 기반 자료 구조는 삽입과 삭제의 한계점이 명확하다"고 할 수 있다.
연결리스트
일반적으로 연결 리스트는 구조체와 포인터를 함께 사용하여 구현한다. 연결 리스트는 리스트의 중간 지점에 노드를 추가하거나 삭제할 수 있어야 한다. 필요할 때 마다 동적 할당을 이용해 메모리 공간을 할당 받는다.
단일연결리스트
단일 연결리스트는 다음과 같은 형태로 나타낼 수 있다. 포인터를 이용해 단방향적으로 다음 노드를 가리킨다.
하나의 구조체 안에 2개의 변수가 들어가도록 하는데, 이중 하나는 포인터 변수로서, 다음 구조체를 가리킨다.
포인터를 이용해 단방향적으로 다음 노드를 가리킨다. 일반적으로 연결 리스트의 시작 노트를 헤드(Head)라고 하며 별도로 관리한다. 다음 노드가 없는 끝 노드의 다음 위치 값으로는 NULL을 넣는다.
연결리스트 구조체 만들기
#include <stdio.h>
#include <stdlib.h>
typedef struct {
int data;
struct Node *next; //그 다음 노드를 가리키는 포인터 변수
} Node; // 구조체 이름 설정
Node *head; //일반적인 연결리스트는 head 노드로부터 출발연결리스트 구조체 사용해보기
int main(void){
Node (*head) = (int*)malloc(sizeof(Node));
Node (*node1) = (int*)malloc(sizeof(Node));
node1->data = 1;
Node (*node2) = (int*)malloc(sizeof(Node));
node2->data = 2;
head->next = node1;
node1->next = node2;
node2->next = NULL; // 항상 끝 노드는 NULL의 값을 가리켜서, 더 이상의 연결된 게 없다는걸 알려야한다.
Node *curr;
curr = head->next; // Node *curr = head->next; 로 대체할 수 있다.
//하나의 포인터를 별도로 만들어서, head의 next를 가리키게 만든다.
//이 curr라는 변수를 이용해, 전체 원소의 값들을 하나씩 다 출력할 수 있게 할 것.
while ( curr !=NULL){
printf("%d ",curr->data);
curr = curr->next;
}
system("pause");
return 0;
}1 2
연결 리스트 삽입과정
단방향 연결리스트에서 특정 위치에 노드를 삽입할 때는 반드시 다음과 같은 순서에 맞게 진행해야한다.
ex)첫번째 위치에 노드를 삽입하는 과정
위의 순서대로 연결 리스트 삽입 함수 addNode()를 만들어 보면, 다음과 같다.
void addNode (Node *root, int data){
Node (*newnode) = (int*)malloc(sizeof(Node));
newnode->data = data;
newnode->next = root->next;
root->next = newnode;
}삽입할 위치가 되는 기준점 노드인 root와 새로 삽입할 newnode에 들어갈 data, 총 2개 변수를 받는 함수이다. 먼저 삽입한 노드를 만들고 메모리를 동적 할당한 후, 삽입할 노드에 들어갈 데이터를 넣는다. 그 후 삽입할 노드가 가리킬, 기준점 다음의 노드를 가리키게 하고, 기준점 노드가 삽입할 노드를 가리키게 한다. 이를 실제로 사용해 본 결과는 다음과 같다.
#include <stdio.h>
#include <stdlib.h>
typedef struct {
int data;
struct Node *next;
} Node;
Node *head;
void addNode (Node *root, int data){
Node (*newnode) = (int*)malloc(sizeof(Node));
newnode->data = data;
newnode->next = root->next;
root->next = newnode;
}
int main(void){
Node (*head) = (int*)malloc(sizeof(Node));
Node (*node1) = (int*)malloc(sizeof(Node));
node1->data = 1;
Node (*node2) = (int*)malloc(sizeof(Node));
node2->data = 2;
head->next = node1;
node1->next = node2;
node2->next = NULL;
Node *curr;
curr = head->next;
while ( curr !=NULL){
printf("%d ",curr->data);
curr = curr->next;
}
printf("\n");
addNode(node1,7);
curr = head->next;
while ( curr !=NULL){
printf("%d ",curr->data);
curr = curr->next;
}
system("pause");
return 0;
}
1 2
1 7 2
연결리스트 삭제 과정
삭제 역시 위의 과정을 철저히 따라야 한다. 연결 리스트 중 특정 노드를 삭제하는 기능을 실행하는 함수는 다음과 같이 만들수 있다.
void removeFront(Node *root){
Node *front = root->next;
root->next = front->next;
free(front);
}위의 함수는 기준점이 되는 root 노드를 인자로 받는다. 이 함수는 root 노드 다음에 오는 노드를 'front'라고 이름 지어서 해당 노드를 위의 도식에 나온 순서에 맞게 삭제한다. 이 함수를 사용한 결과는 다음과 같다.
#include <stdio.h>
#include <stdlib.h>
typedef struct {
int data;
struct Node *next;
} Node;
Node *head;
void addNode (Node *root, int data){
Node (*newnode) = (int*)malloc(sizeof(Node));
newnode->data = data;
newnode->next = root->next;
root->next = newnode;
}
void removeFront(Node *root){
Node *front = root->next;
root->next = front->next;
free(front);
}
int main(void){
Node (*head) = (int*)malloc(sizeof(Node));
Node (*node1) = (int*)malloc(sizeof(Node));
node1->data = 1;
Node (*node2) = (int*)malloc(sizeof(Node));
node2->data = 2;
head->next = node1;
node1->next = node2;
node2->next = NULL;
Node *curr;
curr = head->next;
while ( curr !=NULL){
printf("%d ",curr->data);
curr = curr->next;
}
printf("\n");
addNode(node1,7);
curr = head->next;
while ( curr !=NULL){
printf("%d ",curr->data);
curr = curr->next;
}
printf("\n");
removeFront(head);
curr = head->next;
while ( curr !=NULL){
printf("%d ",curr->data);
curr = curr->next;
}
system("pause");
return 0;
}
1 2
1 7 2
7 2
위에서 볼 수 있듯이, 연결 기반 리스트가 기존의 '배열 기반 리스트'보다 삽입과 삭제가 훨씬 더 간단하다.
