Linked List (연결 리스트)

✅ Linked List (연결 리스트)란?

 

기본 형태

각 노드가 데이터와 링크를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조

---

노드

노드의 구성

 

Data : 값을 저장

Link : 다음 주소를 가리키는 공간

 

 

위 그림과 같이 노드는 Data를 저장하는 공간과 다음 주소를 가리키는 공간이 필요하다. 사용자가 입력하는 정보를 Data공간에 담고 노드가 추가될 때마다 Link를 통해 다음 노드와 연결하는 것이다!

 

---

좀더 자세히 알아보자!

Linked List(연결리스트)는 노드로 연결되어있다고 했다.

하지만 각 노드는 연속된 공간에 저장되어 있지 않고 메모리의 여러 부분에 분포되어 있다.

그래서 각 노드에 다음 노드의 주소를 저장함으로써 다음 노드를 탐색할 수 있다.

(예를 들면 전화를 하면 각 부서로 연결해주는 듯한 타고 타고 넘어가는 느낌..!) 

처음 노드를 Head라고 하고, 마지막 노드를 Tail이라고 하는데 Null을 가리킴으로써 마지막임을 알 수 있다.

 

연결리스트는 데이터를 찾으려면 Head부터 시작해서 링크를 타고타고 들어가서 원하는 데이터를 찾아야한다.

또한 현재 위치에서 전 주소를 가는 것은 불가능하다(이중 연결 리스트는 가능)

불편해보이지만 이러한 자료구조가 생긴 이유는 무엇일까? 바로 데이터를 추가, 삭제할 때 매우 효율적이다.

 

배열의 경우는 접근이 빠르지만 수정하기가 매우 어렵다.

연결 리스트의 경우는 접근은 느리지만 수정이 매우 쉽다.

바로 링크만 끊어주고 새로운 데이터에 연결해주면 되기 때문이다!

그래서  데이터 탐색이 많이 필요한 경우에는 배열을,  데이터 삽입,삭제가 많은 경우 연결 리스트를 사용한다.

 

 

연결리스트의 수정

 

배열과 연결리스트의 비교

LInked List (연결 리스트)	Array (배열)
논리적 순서에 따라 데이터 입력	논리적 순서에 따라 순차적으로 데이터 입력
물리적 순서 = 동적	물리적 주소 = 순차적
인덱스 대신 현재 위치의 전 후 위치를 기억	인덱스를 가져 데이터 접근 속도가 빠름
한 번에 데이터 접근 불가 >>> 링크를 따라가야만 함	한 번에 데이터 접근 가능
데이터 삽입, 삭제 용이

---

메서드

.addToTail() : Linked list의 가장 끝(tail)에 새로운 node를 추가한다.
.removeHead() : 가장 앞(head)를 삭제할 때 사용한다.
.contains : node.value가 존재하는 지 확인한다.

 

활용

• 음악 플랫폼

---

추가적으로 이중 연결 리스트, 원형 연결 리스트 등도 존재한다!