[자료구조] 연결리스트(Linked List)란?

개요

---

Linked List란 모든 노드들이 자신의 값과 나의 다음 값을 pointing하는 자료구조이다.

---

왜 사용하는가?

---

해당 자료구조를 왜 사용하는지 간단한 예시를 들겠다.

---

사진 1

예를 들어, 이러한 모양의 배열이 있는데 현재 나는 4와 6 사이에 5라는 값을 넣고 싶다.

이럴땐 어떻게 해야할까?

---

사진 2

사진 2와 같이 6과 8을 오른쪽으로 밀어서 공간을 확보한다.

---

사진 3

공간을 확보한 후 5를 insert 한다.

 

얼핏 보면 이게 당연한 것처럼 느껴질 수 있다.

하지만 해당 방법은 굉장히 비효율적이다.

 

이러한 번거로움을 해결하기 위한 자료구조가 Linked List 즉 연결리스트이다.

---

Linked List의 구조

---

Linked List는 하나의 메모리 공간(Node)에 데이터와 포인터를 저장한다.

그렇다면 이 자료구조를 사용해서 위의 비효율적인 부분을 어떻게 개선할 수 있을까?

사진 4

사진 4는 Linked List를 아주 쉽게 표현한 예시 사진이다.

현재 사진에서 나는 44라는 Node를 지우고 싶다.

위의 방법대로라면 44라는 Node를 지운 후 30, 9, 15의 값을 가진 Node를 다시 왼쪽으로 옮겨야 한다.

 

사진 5

하지만 Linked List에서는 44라는 값을 뺄 때 그저 값을 지운 후 연결만 해주면 된다.

때문에 배열보다 삽입/삭제가 훨씬 빠르다.

 

사진 6

44라는 Node는 Linked List에서 오른쪽과 같이 표현된다. 화살표는 그 다음 값을 가르키는 pointer를 의미한다.

만약 다음 값이 없다면 NULL을 반환한다.

 

전체적인 구조는 head 포인터와 Linked List의 길이를 저장하는 정수형 변수로 구성된다.

head 포인터는 이 Linked List의 어디가 시작점인가를 지칭한다.

head 포인터의 주소값은 반드시 기억해야한다.

---

구현

---

먼저 Node와 Linked List의 전체적인 구조를 만든다.

typedef int Data;

typedef struct _Node
{
	Data item;
	struct _Node* next;
}Node;

typedef struct
{
	Node* head; //어디가 시작점인가를 지칭
	int len; //전체 Linked List의 길이
}LinkedList;

먼저 Data를 선언한다.

해당 코드는 정수를 담기 위해 int로 선언되었지만, 자료형은 원하는대로 선언할 수 있다.

그리고 Node의 구조와 Linked List의 구조를 구조체로 선언한다.

 

첫 번째로 Node의 구조를 만든다. Node에는 다음 Node를 가르킬 포인터 변수가 들어가야 한다.

 

두 번째로 Linked List의 전체적인 구조를 만든다.

앞서 설명했던 것처럼 먼저 Linked List의 시작점을 가르키는 head라는 포인터 변수를 선언한 후 전체 Linked List의 길이를 담을 정수형 변수를 선언한다.

head에는 데이터를 저장하지 않는다.