[알고리즘] Linked List ( List / Linked List 란? )

1. 리스트 (List)

- 너무 작게 선언하자니 일을 제대로 할 수가 없고 무장정 크게 선언하자니 메모리가 울 것 같습니다.

이 문제를 해결하기 위해 필요한 것은 배열처럼 데이터 집합을 보관하는 기능을 가지면서도 한편으로는 배열과는 달리

유연하게 크기를 바꿀 수 있는 자료구조입니다.

 

이것을 리스트(List : 목록)라고 부릅니다.

 

리스트는 스택과 큐, 그리고 트리와 같은 자료구조를 이해할 수 있는 기반이 된다는 점에서 중요한 의미를 가집니다.

 

 

2. 링크드 리스트 (Linked List)

링크드 리스트는 노드를 연결해서 만드는 리스트라고 해서 붙여진 이름입니다.

리스트 내의 각 요소는 노드(Node), 즉 마디라는 뜻입니다.

 

링크드 리스트의 노드는 다음과 같이 데이터를 보관하는 필드와, 다음 노드와의 연결 고리 역할을 하는 포인터로 이루어집니다.

https://www.geeksforgeeks.org/singly-linked-list-definition-meaning-dsa/

데이터와 포인터로 이루어진 노드들을 다음 그림처럼 엮으면 링크드 리스트가 되는 것입니다.

 

리스트의 첫 번째 노드를 헤드(Head : 머리)라 하고 마지막 노드를 테일(Tail : 꼬리)이라고 합니다.

 

데이터가 늘어날 때마다 노드를 만들어 테일에 붙이면 되기 때문에 다뤄야 하는 데이터 집합의 크기를 미리 알지 못한다 해도 걱정할 필요가 없다. 

 

 

C언어로 표현하는 링크드 리스트의 노드

struct Node
{
	int Data; /* 데이터 필드 */
    struct Node* NextNode; /* 다음 노드를 가리키는 포인터 */
};

Data 자료형이 예시에서는 int이지만, 필요한 자료형으로 바꿔서 사용하시면 됩니다.

 

이렇게 정의된 Node 구조체의 인스턴스를 만들려면 귀찮은 struct 키워드를 동반해야 합니다.

struct Node MyNode;

 

따라서 우리는 다음과 같이 typedef 키워드를 사용해서  Node 구조체를 정의하여 사용할 것입니다.

typedef struct MyNode;
{
	int Data;
    struct tagNode* NextNode;
}Node;

이렇게 선언한 Node 구조체는 struct 키워드 없이 다음과 같이 간편하게 인스턴스를 만들 수 있습니다. 

Node MyNode;