🗂️ 자료구조 공부하기 3 | 연결 리스트 (Linked List)

 

 

 

연결 리스트(Linked List)

 

연결 리스트는 크기가 동적인 자료구조로, 자료구조를 구성하는 요소인 노드(Node)의 연결로 이루어진 자료구조이다.  연결 리스트에 값이 들어올 때마다 노드를 만들어 저장하게 된다. 

 

 

노드(Node) 

노드는 자료구조를 구성하는 요소들을 가리키는 데, 노드의 구성은 크게 링크, 데이터 필드로 구성되어있다.

 

링크는 이 노드가 어디에 위치하고 있는지 알려주는 연결고리이다. 

 

 

리스트(List) 자료구조

연결 리스트를 이해하기 전에 리스트 자료구조를 이해해보자.

List는 Dynamic Array로 동적인 어레이를 뜻한다. 데이터가 들어올 때마다 동적으로 메모리를 할당하는 자료구조이다. 

 

리스트 자료구조가 아닌 정적인 어레이(배열) 를 사용하면 딱 우리가 지정해준 만큼의 공간을 사용해야 한다. 그렇기 때문에 인덱스 번호를 사용하여 관리하기 쉽다는 장점이 있지만, 얼마나 값들이 들어올지 미리 알아야 하므로 유연하지 않다. 하지만 리스트 자료구조를 사용하면 공간이 유동적으로 확보가 되기 때문에 값이 없다면 크기를 줄이고, 값이 많다면 크기를 늘려 공간을 확보할 수 있기 때문에 공간을 더 효율적으로 사용할 수 있다. 

 

즉, 링크드 리스트는 엘리먼트(노드)와 엘리먼트(노드) 간의 연결(링크)을 이용해 리스트 자료구조를 구현한 것이다. 

 

실생활에서는 음악 플레이 리스트에서 자동으로 다음 음악이 재생될 때 사용된다.

 

 

 

링크드 리스트(Linked List) 종류

링크드 리스트 자료 구조도 링크를 어떻게 연결지어 저장하는지에 따라 종류가 나뉜다. 크게 3가지로 볼 수 있다.

 

- Single Linked List

 

싱글 링크드 리스트는 노드와 다음 링크를 알려주는 링크가 하나밖에 없는 자료구조이다. 한 방향으로 자료구조가 연결되어 있다. 자료구조 상 앞으로 가다가 다시 뒤로 돌아올 수 없다. 이전 노드로 돌아갈 수 없다는 단점이 있다. 

 

 

 

- Double Linked List

더블 링크드 리스트는 싱글 링크드 리스트의 단점을 해결한다. 노드 당 앞,뒤로 링크 2개 양방향으로 연결되어 있어서 다시 이전 노드로 돌아갈 수 있다. 

 

 

- Circular Linked List

 

환영 링크드 리스트는 마지막 노드가 첫 번째 노드를 가리켜서 계속 회전할 수 있게 만들어진 자료구조이다. 환영 링크드 리스트는 싱글이거나 더블 링크드 리스트일 수 있다. 

 

 

Array vs List 

 

그럼 리스트는 항상 좋은 것일까? 

- 인풋 사이즈(얼마나 들어오는지) 모르는 상황 :  Array < List (유동적으로 메모리 할당을 조절할 수 있는 리스트가 더 유리하다)

- 데이터 하나당 소모되는 메모리 양 : Array < List (링크는 하나당 4 byte를 차지하기 때문에 어레이가 더 적다)

- 중간 데이터를 추가, 삭제할 때 : Array < List (어레이의 경우에는 중간에 값을 추가하거나 삭제하게 되면 인덱스 번호를 전부 당기거나 한 칸씩 뒤로 이동시켜주어야 한다. 하지만 리스트의 경우는 링크의 연결만 바꿔주면 되기 때문에 더 유리하다) 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

[참고자료]

 

 

리스트 (List) - Data Structure (자료구조)