[자료구조] 연결 리스트
✔️ 연결 리스트란?
연결 리스트는 앞에 아무것도 붙지 않은 Linked List 라는 개념이다.
연결 리스트는 배열처럼 *선형 자료 구조를 가지고 있다.
*선형: 선형, 선형 자료 구조라는 것은 하나의 자료 뒤에 하나의 자료가
존재하는 것으로, 앞 뒤 관계가 1:1의 선형 관계를 가지고 있다.
대표적으로 배열과 리스트를 예시로 들며, 스택과 큐도 해당된다고 한다.
이러한 선형 구조로 된 연결 리스트는 배열하고는 다르게,
인접한 위치에 저장되는 것이 아닌 요소는 포인터를 사용해 연결된다.
여기에는 연결된 노드가 포함되며, 각 노드는 다음 노드의 데이터와 주소를 저장한다.
연결 리스트를 도식화한 발로 그린 그림이다.
여기서 Head가 A라는 곳에 접근하게 되면, (이것을 항상 머리노드(Head)라고 한다)
노드는 다음 노드의 데이터와 주소를 저장하고 나서 B라는 요소에 포인터를 사용하여
연결하게 되고 연결된 마지막에는 NULL을 가리키게 된다.
그리고 이것을 끝 노드는 꼬리노드(Tail)를 가리킨다고 한다.
이러한 개념이 나오게 된 이유에는 배열에는 여러가지 제한이 따르기 때문이다.
배열의 크기는 고정되어있고, 새로운 요소를 삽입하려는 과정에서 기존의 요소를
삭제하는 비용이 많이 들기 때문에 연결 리스트라는 개념이 등장했다고 한다.
이러한 연결 목록의 유형으로는 우리가 공부할 이중 연결 리스트 외에도
단순 연결 리스트(Simple Linked List)와 원형 연결 리스트(Circular Linked List)가
존재하며 앞선 단점을 해결한 동적인 배열임과 동시에 삽입과 삭제가 용이하다는
장점을 가지고 있다.
✔️ 연결 리스트.c
위에 도식화한 그림을 C언어 코드를 통해서 살펴볼 수 있다.
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
};
int main()
{
struct Node* head = NULL;
struct Node* a = NULL;
struct Node* b = NULL;
struct Node* c = NULL;
head = (struct Node*)malloc(sizeof(struct Node));
a = (struct Node*)malloc(sizeof(struct Node));
b = (struct Node*)malloc(sizeof(struct Node));
c = (struct Node*)malloc(sizeof(struct Node));
head->data = 1;
head->next = a;
a->data = 2;
a->next = b;
b->data = 3;
b->next = c;
c->data = 4;
c->next = NULL;
return 0;
}
총 4개의 노드가 있는 연결 리스트를 C 코드로 간단하게 구현해보았다.
앞서 노드에 저장하는 데이터는 int 형으로 선언해주고,
next를 나타내는 노드는 구조체 포인터로 선언하게 된다.
각 구조체 포인터에 대한 변수로 head, a, b, c를 NULL 값으로 저장한다.
stdlib.h 헤더 파일에 선언된 malloc 함수를 통해서 메모리를 동적으로 할당해주는데,
해당 값들은 힙 영역에 접근하여 할당하게 된다.
여기서 구조체 Node의 크기만큼인 sizeof 함수를 통해 크기를 얼만큼 할당할지를 정해주고,
malloc 함수는 리턴 값으로 void형 포인터를 리턴하기 때문에 해당 void*에서 struct*로
변환이 이루어진 값에 대하여 각 head, a, b, c에 대입하게 된다.
구조체 포인터가 가리키는 주소에 데이터를 할당하기 위해서는
코딩도장에서 공부한 것처럼 화살표 연산을 사용하게 된다.
다시금 기억하자면 화살표 연산은 구조체 포인터 안에 있는 멤버 변수에
접근할 수 있도록 하는데, 포인터명->멤버변수명 = 값; 처럼 사용하게 된다.
또는, (*포인터명).멤버변수 = 값; 처럼도 사용할 수 있다.
이렇게 구성된 구조를 통해 다시한번 도식화하면
다음과 같이 표현할 수 있다.
① HEAD라는 첫 번째 노드에 1이라는 데이터가 할당되게 되면,
A라는 두 번째 노드에 첫 번째 노드를 연결하게 된다.
② 그 다음 노드가 가리키는 두 번째 노드의 데이터 영역에
2라는 데이터가 할당되고 B라는 세 번째 노드에 두 번째 노드를 연결한다.
③ 그 다음 노드가 가리키는 세 번째 노드의 데이터 영역에
3이라는 데이터가 할당되고 C라는 네 번째 노드에 세 번째 노드를 연결한다.
④ 마지막으로 가리키는 네 번째 노드의 데이터 영역에
4라는 데이터가 할당되고 NULL을 가리키게 되면서 연결된 노드는 끝이난다.
이렇게 나열된 노드는 정상적으로 출력되는지 확인할 수 있다.
간단하게 while 반복문을 통해 출력해보면서 위에서 설명한 것같이
화살표 연산이 아닌 이번에는 직접 멤버변수에 접근하여 값을 할당해주었다.
할당해준 값이 선형 구조로 나열되어 연결 리스트처럼,
그리고 그림처럼 해당 값들이 정상적으로 출력되었다.
다음은 연결 리스트의 유형이었던
이중 연결 리스트에서 공부해보려고 한다.
화이팅 💪