연결리스트(Linked List)란?
데이터를 순서대로 나열한 자료구조로 순서가 있는 데이터를 관리할 때 사용한다.
배열처럼 메모리상에 연속적으로 위치하지 않으며 각 데이터는 포인터로 연결되어 있어 데이터끼리 물리적으로
떨어져 있어도 된다.
노드(node)와 링크(link)를 구조화시킨것인데 노드란 데이터를 담고 있는 그릇이며 링크는 순서유지를 위한
연결고리이다.
메모리동적할당을 기반으로 구현된 리스트이며 배열에 비해 추가 / 삭제가 용이한 점이 있지만 특정 데이터를
찾기 위해서는 순차 탐색을 하므로 탐색속도가 느리며 추가적인 포인터 변수 사용으로 메모리 공간이 낭비된다는
단점이 있지만 동적할당을 기반으로 한 리스트이기 때문에 크기를 미리 지정할 필요가 없다는 장점이 있다.
연결리스트는 데이터를 선형적으로 저장하고 처리하는 한 방법이고 기존에 배열을 이용했을 때 보다 삽입과 삭제가
많은 경우에서 효율적이다. 다만, 특정한 인덱스에 바로 참조해야 하는 처리과정이 많다면 배열을 이용하는것이
효율적이다.
일반적으로 연결리스트는 구조체와 포인터로 사용하게 되는데 리스트의 중간지점에 노드를 추가하거나 삭제할 수
있어야 하고 필요할때마다 메모리공간을 할당받는다.
단일 연결리스트는 포인터를 이용해 단방향으로 다음 노드를 가리킨다.
data | next -> data | next -> data | next
이런 형태인데 하나의 구조체안에 데이터를 담는 변수와 다음노드를 가리키는 포인터 변수인 next가 들어가게 된다.
이때 일반적으로 연결리스트의 시작 노드를 헤드(Head)라고 하며 별도로 관리하며 다음노드가 없는 끝 노드의
다음 위치값은 NULL을 넣어준다.
next가 NULL이 된다면 그 리스트는 더이상 노드가 존재하지 않는 리스트의 마지막이라고 알려주는 것이다.
배열로 처리
#define _CRT_SECURE_NO_WARNINGS
#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]);
}
printf("\n");
}
void removeAt(int index){
for(int i = index; i < count - 1; i++){
arr[i] = arr[i + 1];
}
count--;
}
int main(void){
addFirst(4);
addFirst(5);
addFirst(1);
addBack(7);
addBack(6);
addBack(8);
removeAt(3);
show();
system("pause");
return 0;
}위 예제는 배열형태로 처리하면서 제일 앞이나 제일 뒤에 값을 추가해주고 원하는 인덱스의 값을 삭제해주는
예제이다.
결과값은 1 5 4 6 8 이 출력되게 된다.
addFirst의 경우는 처음 값이 들어갈때를 제외하고는 반복문을 실행하게 된다.
첫 값인 4를 넣어주고 나면 count가 증가되기 때문에 다음 5를 넣어줄때는 반복문에 의해 arr[i] = arr[i - 1]이
처리되는데 이때를 예로 들면 arr[1] = arr[0] 이 되는것이고 그럼 arr[1] = 4 라는 것이나 마찬가지다.
0에 있던 첫번째 값인 4를 뒷칸으로 넘겨주고 나면 i는 다시 0이 되기 때문에 반복문을 빠져나오게 되는데
arr[0] 과 arr[1]은 4의 값을 갖고있는 상태로 빠져나온다.
그럼 첫번째 인덱스에 새로운 값을 넣어줘야 하기 때문에 arr[0] = data로 새로운 값인 5를 추가하게 되는것이다.
그리고 마찬가지로 count값을 증가.
count값을 계속 증가시키고 반복문에서 한 회차마다 i를 빼줘야 하는 이유는 앞 인덱스부터 뒤 인덱스로 밀어내는것이
아닌 뒤 인덱스에서 앞 인덱스의 값을 끌어당겨줘야 제대로 처리가 되기 때문이다.
앞 인덱스의 값을 먼저 뒤 인덱스로 넘겨버리면 그 뒤 인덱스의 값은 그대로 사라져버리기 때문이다.
addBack의 경우는 제일 뒤에 추가해주는 것이기때문에 복잡할 것 없이 데이터만 추가해주게 된다.
removeAt은 삭제하고자하는 인덱스번호를 받아서 처리하게 되는데 지우고자 하는 인덱스의 뒤에있는 값들을
앞으로 당겨서 중간에 삭제한 인덱스가 출력되지 않도록 하기 위해서다.
이 예제에서는 사실 삭제한다기보다는 덮어씌운다는 표현이 맞다.
반복문을 살펴보면 3이라는 인덱스 번호를 받아오게되고 i = 3, count = 6 - 1이 된다.
그럼 지우는 값인 3번인덱스인 arr[3]에 arr[4]값을 덮어 씌워야 하기 때문에 arr[i + 1]로 처리하게 되는것이고
i를 증가시킴으로써 뒤에있는 인덱스들 역시 하나씩 앞으로 당겨주게 된다.
그리고 count는 결국 현재 배열 인덱스의 마지막 번호인것이므로 반복문이 끝난 후에는 감소를 시켜주어야
출력을 위한 함수인 show()에서 원하는 값만 출력이 가능하다.
여기서 만약 show()에서 count 에 + 1을 해준다면 1 5 4 6 8 8이 출력된다.
위에서 얘기했다시피 삭제한다기보다는 덮어씌운다는 의미가 이것이다. 그냥 값을 하나씩 앞에다가 복사하면서
붙여준것 뿐 정말 삭제한것이 아니기 때문이다.
여기서 좀 한참 고민했었는데 만약 그 뒤에도 값이 나오지 않게 하고 싶다면?
그럼 removeAt에서 count - 1이 아닌 count로하면 1 5 4 6 8 0 이렇게 출력된다.
기본적으로 모든 인덱스에 0이 들어가있는 상태이기 때문에 또 그 뒤에 있던 인덱스의 값을 가져왔기 때문에
0이 출력되는 것이다.
하지만 문제가 될 수 있는 부분은 지금은 배열 크기가 10000인데 7자리만 사용했으니까 가능한거고 만약
6만큼의 크기의 배열에서 이렇게 작성하면 오류가 발생한다.
크기가 6인 배열의 최대 인덱스는 5가 되어야 되는데 removeAt에서 arr[i + 1]을 하며 6번 인덱스를 찾으라고 하기
때문에 오류가 발생하게 된다.
자바로 코딩테스트 문제들 풀때 겪었던 오류부분인데 혹해서 작성하면 실수할 수 있는 부분이다.
이렇게 배열기반 리스트는 배열로 만들었기 때문에 특정한 위치의 원소에 즉시 접근할 수 있다는 장점이 있지만
데이터가 들어갈 공간을 미리 메모리에 할당해야 한다는 단점이 있으며 원하는 위치로의 삽입이나 삭제가
비효율적이다.
연결리스트
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
typedef struct{
int data;
struct Node *next;
} Node;
Node *head;
int main(void){
head = (Node*)malloc(sizeof(Node));
Node *node1 = (Node*)malloc(sizeof(Node));
node1->data = 1;
Node *node2 = (Node*)malloc(sizeof(Node));
node2->data = 2;
head->next = node1;
node1->next = node2;
node2->next = NULL;
Node *cur = head->next;
while(cur != NULL){
printf("%d ", cur->data);
cur = cur->next;
}
system("pause");
return 0;
}위 코드는 전체적인 구조만을 파악하기 위한 코드이다.
Node라는 구조체를 만들어주고 기본적으로 동적할당을 이용함으로써 필요한 메모리를 할당받도록 한다.
head, node1, node2 라는 노드를 만들고 메모리 할당을 받은 후 node1에는 1, node2에는 2라는 값을 넣어준다.
head->next = node1; 이라는 것은 head라는 노드의 next는 node1이 된다는 것이고
next를 이용해 head의 다음 노드를 node1으로 연결해주는 것이다.
node2는 마지막 노드이기 때문에 next로 NULL을 넣어주는 것이다.
cur은 출력을 위해 만들어준 것이고 출력을 위해 head의 next 인 node1을 가리키도록 한다.
cur->data로 출력하게 되면 결국 node1의 data를 출력하게 되고 cur->next로 다음 노드인 node2도 출력하게 된다.
삽입, 삭제과정
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
typedef struct{
int data;
struct Node *next;
} Node;
Node *head;
void addFront(Node *root, int data){
Node *node = (Node*)malloc(sizeof(Node));
node->data = data;
node->next = root->next;
root->next = node;
}
void removeFront(Node *root){
Node *front = root->next;
root->next = front->next;
free(front);
}
void freeAll(Node *root){
Node *cur = head->next;
while(cur != NULL){
Node *next = cur->next;
free(cur);
cur = next;
}
}
void showAll(Node *root){
Node *cur = head->next;
while(cur != NULL){
printf("show : %d ", cur->data);
cur = cur->next;
}
}
int main(void){
head = (Node*)malloc(sizeof(Node));
head->next = NULL;
addFront(head, 2);
addFront(head, 2);
addFront(head, 2);
addFront(head, 2);
addFront(head, 2);
removeFront(head);
showAll(head);
freeAll(head);
system("pause");
return 0;
}제일 앞부분의 삽입하는 addFront와 제일 앞 노드를 삭제하는 removeFront, 전체 삭제하는 freeAll로 작성하였다.
기본 삽입 처리는 head - node1 - node2 - NULL 이런 형태의 구조에서 node7을 맨 앞에 넣어주고 싶다면
head의 next를 node7에 연결하고 node7의 next를 node1로 연결해주면 된다.
addFront에서 node를 동적할당 받고 그 node의 data에는 함수로 넘겨준 data값을 넣어준다.
그리고 그 node의 next는 root로 받은 head의 next에 연결하도록 하고
root의 next는 해당 node로 연결하도록 하면 된다.
위에서 예시로 써둔 node7이 삽입되는 과정으로 설명한것과 같은 형태이다.
삭제과정은 삭제 노드의 이전노드가 삭제노드의 next를 가리키도록 하면 된다.
위 코드에서는 제일 첫번째 노드를 삭제하도록 했다.
그래서 root라는 head에 해당하는 노드를 받아 처리한다.
front라는 노드를 새로 만들고 그 노드는 root의 next에 연결되어있는 노드로 정의한다.
그럼 삭제하고자하는 head의 다음 노드가 front가 되고 root의 next를 front의 next로 연결해준다.
그럼 head는 front의 다음 노드를 가리키게 되고 front와의 연결이 끊어진다.
그 후 free()를 이용해 front의 메모리할당을 해제해준다.
freeAll의 경우는 전체적으로 메모리할당을 해제해서 리스트 자체를 지운다면 이렇게 해야한다
이런 느낌으로 강의에 넣으신것 같다.
head의 next로 정의한 cur을 이용하며 마지막 값인 NULL을 만날때까지 반복하도록 반복문을 작성하고
cur = cur->next로 다음 노드로 넘어가며 모든 노드를 메모리할당 해제하도록 한다.
코드에서는 next라고 따로 만들어서 처리했지만 결국 같은 의미이다.
양방향 연결리스트
양방향 연결리스트는 머리(head)와 꼬리(tail)을 모두 가진다는 특징이 있다.
각 노드는 앞 노드와 뒷 노드의 정보를 모두 저장하고 있다.
prev | head | next <- -> prev | node1 | next <- -> prev | node2 | next <- -> prev | tail | next
이런 형태이다.
양방향 연결리스트에서의 삽입은 삽입하고자하는 위치에 있는 노드의 next값이 삽입하는 노드의 prev를 향하도록
하고 삽입하는 노드의 prev역시 해당 노드의 next를 향하도록 한다. 그 후 삽입하고자 하는 노드의 다음 노드의
prev가 삽입 노드의 next를 향하도록 하고 삽입노드 역시 다음노드의 prev를 향하도록 하면 된다.
이 순서가 중요하다고 한다. 기본적으로 순서를 철저하게 잘 지키고 고려해야 안정적으로 끊김없이 리스트가
이어질 수 있기 때문이다.
head - node1 - node2 - tail 이 형태에서 node1과 node2 사이에 node7을 삽입한다면
1. node1 | next -> prev | node7
2. node1 | next <- -> prev | node7
3. node7 | next <- prev | node2
4. node7 | next <- -> prev | node2
위의 순서대로 처리해야 한다.
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
typedef struct{
int data;
struct Node *prev;
struct Node *next;
} Node;
Node *head, *tail;
void insert(int data){
Node *node = (Node*)malloc(sizeof(Node));
node->data = data;
Node *cur;
cur = head->next;
while(cur->data < data && cur != tail){
cur = cur->next;
}
Node *prev = cur->prev;
prev->next = node;
node->prev = prev;
cur->prev = node;
node->next = cur;
}
void removeFront(){
Node *node = head->next;
head->next = node->next;
Node *next = node->next;
next->prev = head;
free(node);
}
void show(){
Node *cur = head->next;
while(cur != tail){
printf("%d ", cur->data);
cur = cur->next;
}
}
int main(void){
head = (Node*)malloc(sizeof(Node));
tail = (Node*)malloc(sizeof(Node));
head->next = tail;
head->prev = head;
tail->next = tail;
tail->prev = head;
insert(2);
insert(1);
insert(3);
insert(9);
insert(7);
removeFront();
show();
system("pause");
return 0;
}삽입과 삭제 그리고 출력하는 코드이다.
삽입은 오름차순 순서로 들어가도록 했고 삭제는 맨 앞 노드를 삭제하도록 했다.
삽입에서는 data만 받고 시작한다. node를 새로 메모리할당받아주고 node의 data에 받아온 data를 넣어준다.
그리고 cur은 head의 next로 정의한다.
그럼 첫 삽입부분에서는 cur은 tail이 된다.
cur의 data가 받아온 data보다 작고 cur이 tail이 아니라면 반복문이 실행되기 때문에 첫 삽입에서는 동작하지 않는다.
prev를 하나 또 만들어서 cur의 prev로 정의하는데 cur은 tail이고 prev는 head가 되기때문에 prev는 head가 된다.
prev의 next를 node로 연결하면 2의 값을 가진 node를 head가 가리키게 된다.
그뒤로 node가 head를 가리키고 tail이 node를 node의 next가 tail를 가리키도록 해준다.
두번째 값을 넣어주는데 두번째 값은 1이다.
그럼 처음 들어가있는 값인 2보다 작기때문에 2 앞에 들어와야 한다.
처음과 동일하게 node로 할당받고 1이라는 값을 넣어준다.
cur은 head의 next인데 그럼 2의 값을 갖고 있는 node가 된다.
cur을 좀 더 보기편하게 node2라고 한다면 node2의 data인 2가 1의 값을 갖고 있는 data보다 작고 node2가 tail이
아니라면 반복문을 실행한다.
node2는 tail이 아니지만 갖고 있는 데이터인 2가 들어올 1보다 크기 때문에 false처리가 되어 반복문이 실행되지 않고
prev는 node2의 prev인 head가 된다.
head의 next를 node1로 연결하고 node1역시 head에 연결. node2를 node1에 연결 후 node1 역시 node2에 연결한다.
다음으로는 3의 값을 넣어주는데 3은 2와 tail사이로 들어가야한다.
node를 할당받고 3을 넣어준다.
node3이라 칭하고 cur은 head의 next인 node1이 된다. 똑같이 cur을 node1이라 하며 설명.
node1의 데이터인 1은 data인 3보다 작다. 그리고 node1은 tail이 아니기때문에 true가 되며 반복문이 동작한다.
cur = cur->next; 가 처리되어 cur = node1->next가 되어 node2가 된다.
하지만 node2의 데이터 역시 3보다 작고 tail이 아니기 때문에 반복문이 한번더 동작하여 cur = node2->next로
tail이 된다. 여기서는 cur이 tail이 되었기 때문에 반복문이 종료된다.
그럼 prev는 cur의 prev이기 때문에 tail의 prev인 node2가 prev가 된다.
node2의 next를 node3로 그럼 node3의 prev를 node2로 연결.
cur은 tail이기 때문에 tail의 prev를 node3에 연결 node3의 next를 tail로 연결한다.
그럼 지금까지의 진행상황으로는 head - node1 - node2 - node3 - tail 형태로 오름차순으로 잘 들어가는것을
확인할 수 있다.
이와같은 형태로 나머지 두 값도 들어가게되어 1 2 3 7 9 형태로 완성된다.
삭제과정이다.
removeFront는 head의 바로 다음 노드를 삭제하는 과정으로 단방향연결리스트에서와 같다.
root로 head를 받냐 안받냐의 차이인데 어차피 head를 이용해 삭제하는것이기 때문에 둘다 같은처리나 마찬가지다.
node는 head의 next값인 node1로 정의한다.
head의 next를 node1의 next인 node2에 연결한다. 그리고 next를 node의 next인 node2로 정의.
next->prev 는 node2의 prev이므로 이것을 head에 연결한다.
그럼 node1의 prev는 head에 next는 node2에 연결되어있지만 head의 next는 node2에 node2의 prev는 head에
연결되어있기때문에 사실상 해제상태이다.
그리고나서 free()를 이용한 메모리해제를 해준다.
양방향이 작업이 많고 중간중간 헷갈리는 부분들이 있어서 구현시에 중간중간 체크가 좀 필요하며 너무 복잡하지 않고
깔끔하게 작성하는것이 중요할것 같다.
레퍼런스
패스트캠퍼스 올인원 패키지 - 소프트웨어 베이직