Linked List

Linked List가 뭘까?

Linked List를 정말로 이해하려면 연결 목록이 어떤 유형의 자료 구조인지 알아야 한다.

Linked List의 한 가지 특징은 선형 자료 구조라는 것인데, 이는 그것들이 어떻게 구성되고 가로지르는지에

대한 sequence와 order가 있다는 것이다. 예를 들어 징검다리를 생각했을때 중간 지점을 가기 위해선

처음 돌부터 해당 지점까지 순차적으로 이동해야한다. 배열, 링크드 리스트 등이 선형 자료 구조이다.

비선형 자료 구조는 항목을 순서대로 정렬할 필요가 없고 비순차적으로 탐색이 가능하다. 해시 테이블

, 트리, 그래프 등이 비선형 자료 구조에 속한다.

 

그렇다면 배열과 링크드 리스트의 차이점이 무엇일까?

가장 큰 차이점은 시스템에서 메모리를 사용하는 방식이다. 

배열이 생성될 때 일정량의 메모리가 필요하다. 배열에 저장해야 하는 7개의 문자가 있는 경우, 해당 배열을

나타내기 위해 7바이트의 메모리가 필요하다. 배열은 하나의 연속적인 블록에 그 모든 메모리가 필요하다.

즉, 컴퓨터에서 배열의 메모리는 모여있고 모두 함께 한 곳에서 찾아야한다.

반면에, 링크드 리스트는 7바이트의 메모리가 한 곳에 모두 필요하지 않다. 뚝뚝 떨어져 있을 수 있다.

링크드 리스트는 단일 메모리 블록을 차지할 필요가 없다. -> 메모리 전체에 흩어져 있을 수 있다.

 

또 근본적인 차이점은 배열은 정적인 자료 구조이고 링크드 리스트는 동적인 자료 구조이다.

정적인 자료 구조는 구조가 생성될 때 모든 리소스를 할당해야 한다. 즉, 구조의 크기가 커지거나 줄어들고 

요소가 추가되거나 제거되더라도 항상 주어진 크기와 메모리 양이 필요하다. 만약 더 크기를 키울려고 하면

요소들을 복사하고 더 많은 메모리로 다시 생성해서 복사한 요소를 넣고 요소를 추가해야 한다. 내부의 요소를

삭제해도 동적인 자료 구조와는 다르게 할당한 메모리가 남아있고 데이터만 비어져있는 것이다.

반면, 동적인 자료구조는 메모리가 줄어들고 커진다. 선언을 할때 정해진 양의 메모리를 할당할 필요가 없고

크기와 모양이 변경될 수 있으며 메모리 양도 변경될 수 있다.

 

배열과 링크드 리스트가 어떤 차이가 있는지 알아봤으니 링크드 리스트에 대해서 더 자세히 알아보자.

링크드 리스트의 요소가 흩어진 메모리에 존재할 수 있다고 했는데

어떻게 각 요소가 모여있지 않고 흩어져 있는데 하나의 변수로 묶여있을 수 있을까?

링크드 리스트는 각각의 노드로 구성된다. 리스트의 시작점은 head라고 하는 첫 번째 노드에 대한 참조(reference)이다.

거의 모든 링크드 리스트엔 head가 필요하다. 왜냐면 이것이 리스트에 진입할 수 있는 유일한 길이기 때문이다.

이게 없다면 어디서부터 시작해야할지 알 수가 없다. 리스트의 끝은 null 혹은 빈 값을 가리키는 노드이다.

각 노드는 해당 노드에 포함된 정보와 다음 노드에 대한 참조(reference)의 두 부분으로 구성된다.

결국 노드는 자신이 가지고 있는 정보와 내 이웃에 대해서만 알고 있는 것이다. 노드는 링크드 리스트의 길이를

알지 못하고 시작과 끝도 모르는 경우가 많을 것이다. 모든 노드는 그저 자신이 가지고 있는 정보와

해당 포인터가 참조하는 노드(다음 노드)와 관련되어 있을 뿐이다.

 

이게 링크드 리스트에서 연속적인 메모리 블록이 필요하지 않은 이유이다.

각 노드엔 '주소' 혹은 다음 노드에 대한 참조가 있기 때문에 배열처럼 바로 옆에 붙어 있을 필요가 없다.

대신 다음 노드에 대한 포인터 참조에 의존해서 목록을 탐색할 수 있다는 사실에 의존한다. 그렇기 때문에

노드가 추가되고 제거하는 것이 자유로울 수 있다.

 

지금까지 우리가 생각한 것은 한 방향으로 쭉 길게 체인처럼 연결된 링크드 리스트일 것이다.

하지만 다음 노드를 참조하는 것처럼 이전 노드에 대한 참조 포인터도 가질 수 있다. 즉, 두 개의 참조가

포함되는 것이다. 그래서 이중 링크드 리스트라고 부른다. 단방향이 아니라 양방향으로 탐색이 가능해

지는 것이다.

그리고 순환 링크드 리스트라는 것이 존재한다. 끝부분이 null 이나 빈 값을 가리키는 것이 아니라 다시

head를 가리키는 것이다. 그렇다면 끝을 어떻게 알 것인가?? 그래서 tail 역할을 하는 노드가 존재한다.

이중 순환 링크드 리스트도 구성할 수 있다.

 

링크드 리스트에 대해서 자세히 알아봤다. 하지만 자료구조에 대해 아는 것보다 상황에 맞게 이 자료구조

라는 도구를 사용해야겠다고 판단하고 제대로 사용하는 것이 중요하다. 사용할 떄와 사용하지 않을 때를

결정하는 것은 굉장히 어렵다. 그렇기에 무엇이 링크드 리스트를 유용하게 만들고 언제 구현을 고려해야

할지에 대해 생각해보자.

링크드 리스트를 배열 대신 사용하는 이유가 무엇일까? 배열은 정적인 자료 구조라서 먼저 메모리를 할당

해놓는다. 이말은 내가 할당해놓은 이 크기를 다 사용하지 않는다면 데이터가 비어있지만 메모리는 할당

되어 있다는 뜻이다. 링크드 리스트는 어떤가? 전혀 그렇지 않다. 데이터를 추가 또는 제거 하면서 내가

원하는 만큼의 메모리를 할당하여 사용할 수 있다. 그리고 배열처럼 복사할 필요없이 추가, 제거가 자유롭다.

 

링크드 리스트는 삽입, 제거의 부분에서 생각했을때 굉장히 이상적인 자료 구조이다. 하지만 어떠한 요소를

검색하고 찾는데 매우 느리다. 하나의 요소를 찾기 위해선 무조건 순차적인 탐색이 이루어져야한다.

그렇다면 많은 순회, 반복 또는 빠른 인덱스 수준의 액세스가 필요한 작업을 수행해야 한다면 링크드 리스트는

최악의 자료 구조가 될 수 있다. 이런 경우는 배열이 더 나은 솔루션이 된다. 배열은 인덱스를 안다면 O(1)로 접근

할 수 있다.

 

참조 - 해당 링크의 내용을 참조하였고 링크엔 이미지가 있어 더 이해하기 쉬울 수 있습니다!!

- https://medium.com/basecs/whats-a-linked-list-anyway-part-1-d8b7e6508b9d

What’s a Linked List, Anyway? [Part 1]

- https://medium.com/basecs/whats-a-linked-list-anyway-part-2-131d96f71996

What’s a Linked List, Anyway? [Part 2]