Linked List

1. 연결리스트(Linked List)란?

 

LinkedList는 Node라는 객체로 이루어져 있는데 Node는 데이터를 저장하는 field와 다음 노드를 가리킬 수 있는 next pointer field로 구성이 되어있습니다.

 

이말인 즉슨, 이 노드들이 연결된 형태의 자료구조를 바로 LinkedList라고 하는 것입니다.

 

예를 들어, 학교에서 어느 반의 모든 학생들의 데이터를 저장한다고 했을 때, 학생 한명 한명의 신상정보 자료를 노드로 만들고, 1번 학생의 신상정보 자료에 2번 신상정보 자료가 어디 있는 지 표시를 해 놓는 방식인 것입니다.

 

쉽게 말해서 줄줄이 소세지마냥 자료를 엮어 놓은 것이라고 생각하면 되겠습니다.

 

 

반면, 배열은 학생들의 데이터를 한 곳에 쭉 쌓아 올린 모양새라고 생각하면 됩니다.

 

그래서 전에 말했듯이 데이터를 추가하거나 삭제 할 때는 쌓아 올린 수가 많은만큼 어려운 것인데, 이 LinkedList는 엮여 져있는 pointer만 조금씩 수정해 주면 해당 과정이 쉽게 가능해져 시간 소모가 다른 것입니다.

 

노드 중에서는 고유한 노드가 존재하며 이 노드들은 다음과 같습니다.

 

Head: 가장 앞에 위치한 노드

• LinkedList의 값이 있더라도 Head 노드는 반드시 비어있습니다. 따라서 head 노드에는 무조건 null값을 주게 됩니다. 그래서 head node는 보통 dummy node라고 불리기도 합니다.(아무런 값이 존재하지 않고 그저 수단으로만 사용되기 때문)

 

Tail: 가장 뒤에 위치한 노드

• Tail은 자신의 다음에 가리킬 노드가 없기 때문에 Tail의 next pointer 또한 null입니다.
• 단순 연결 리스트에서는 노드가 뒤에 계속 추가 된다면 tail 노드는 바뀔 수 있지만, 이중 연결 리스트에서는 tail노드를 따로 지정을 해두기 때문에(이름이 '이중'인 이유) tail노드가 바뀌지 않습니다.

 

2. 검색

LinkedList에서의 검색은 ArrayList의 검색과 마찬가지로 head 노드에서부터 tail 노드까지 순차적으로 순회하면서 데이터를 찾아갑니다. 그렇기 때문에 마찬가지로 O(N)의 시간 복잡도를 가집니다.

 

ArrayList는 대신 index로 검색을 하는 경우 Randon Access(임의 접근 방식)가 가능하여 데이터를 처음부터 찾을 필요가 없기 때문에 O(1)의 시간 복잡도를 갖습니다.

 

 

3. 추가

'추가'는 원하는 노드를 하나 만들고 그 노드와 Tail노드의 next pointer를 연결하는 작업입니다.

마찬가지로 처음부터 끝까지 순회하면서 마지막 노드가 가리키고 있는 Null 위치에 우리가 원하고자 하는 노드를 추가 시키는 개념입니다.

 

 

ArrayList와는 달리, 끝 노드를 찾아야 하지 않아도 되고 그저 tail노드에서 새로운 노드를 추가하는 것이기 때문에 O(1)

의 시간 복잡도를 갖습니다.

 

4. 삽입

삽입은 제일 끝이 아니라 중간에 넣는 경우를 말하며 LinkedList는 ArrayList와는 다르게 데이터를 뒤로 한 칸씩 전부 밀어줄 필요가 없습니다. 그냥 간단히 pointer만 바꿔주면 되기 때문에 논리는 간단하지만 삽입 위치를 찾기 위해서는 순회를 통해 찾아야 하기 때문에 시간복잡도는 O(n) 입니다.

 

 

해당 과정은 다음과 같이 진행됩니다.

 

1. 먼저, 삽입을 원하는 노드를 생성한다.

 

2. 해당 노드의 previous(이전의) node의 next 포인터를 본인 노드와 연결하고 previous node의 next pointer가 가리키고 있던 노드를 본인 노드의 next pointer로 가리킴로써 연결을 삽입을 마무리한다.

5. 삭제

LinkedList에서 삭제하고자 하는 노드가 있을 때는 그 위치를 찾아가야 하기 때문에 결정되는 시간복잡도는 O(N)입니다.

• head와 tail노드로 무작정 알아낼 수 없기 때문

 

ArrayList에서는 삭제할 위치를 찾고 뒤의 데이터들을 앞으로 한 칸씩 당기는데 또 시간이 O(N)만큼 소요가 됐다면,

LinkedList는 데이터를 당겨오지 않고 pointer만 조금 바꾸어 주면 삭제 과정이 자동으로 이루어지게 됩니다.

 

 

빨간 점선으로 된 노드를 삭제해야 한다고 합시다. 앞으로 삭제하고자 하는 노드를 삭제노드, 그 노드의 이전 노드는 이전노드 다음 노드는 다음노드라 부르겠습니다.

 

 

이전 노드의 next pointer는 삭제 노드의 next pointer가 가리키고 있던 노드를 가리키게되고 삭제 노드의 next pointer는 아무것도 가리키지 않는 상태인 null 상태가 되게 합니다.

 

즉, node.next = null; 로 표현할 수 있습니다.

 

 

그 이후 자바에서는 garbage collector에 의해 붕떠 있던 삭제 노드는 알아서 사라지게 됩니다. 그리하여 LinkedList의 삭제를 진행한 후 연결이 잘 되어 있는 것을 볼 수 있습니다.

 

6. Linked List의 장단점

장점

• 배열의 복사나 재할당 없이 데이터 추가 가능 + 유연한 공간
  • ArrayList는 배열이 꽉 차있는 경우 크기를 늘려 준 다음 데이터를 다시 추가해 주는 과정을 진행해야 했는데 LinkedList는 쓰는 공간만큼만 크기가 늘었다 줄었다 하기 때문에 메모리 측면에서 훨씬 효율적입니다.

단점

• 데이터 접근에 대한 시간이 늘어남
  • 배열(Array List)과 달라, Random Access가 되지 않기 때문에 원하는 노드를 찾아야 하는 경우 O(N)의 시간복잡도가 발생한다는 점이 단점이라면 단점이겠습니다.

 

LinkedList vs. Array

	Linked List	Array List
추가	O(1)	O(1), O(N)
삽입	O(N)	O(N)
삭제	O(N)	O(N)
검색	O(N)	O(1)

 

가. 배열

• 배열은 각 값마다 고유한 인덱스를 가지고 있다. 이는 탐색에는 매우 유리하지만 삽입이나 삭제를 하는 부분에서 단점이 있다.
• 예를 들어 [1, 2, 3, 4, 5, 6]이라는 배열에서 3과 5사이에 4를 삽입하고 싶다면 5, 6의 인덱스를 뒤로 한칸씩 밀고 4를 를 빈 자리에 넣어줘야 한다. 이와 같은 과정은 배열의 복사, 이동을 통해 생기며, 삽입, 삭제의 규모가 커진다면 이는 많은 소요를 필요로 한다.

나. LinkedList

• LinkedList는 위와 같은 배열의 단점을 해결하기 위해 나왔다.
• LinkedList에서의 삽입은 삽입할 노드의 위치의 이전노드, 다음노드와 연결만 해주면 되고, 삭제도 마찬가지로 삭제하고 싶은 노드에 연결되어 있는 앞 뒤의 노드를 서로 이어주면 된다.
• 하지만 LinkedList는 탐색을 위해서는 항상 첫번째 노드부터 비교해야 한다는 담점이 있다.
• 위에서 설명한 내용과 같이, 배열과 LinkedList는 장단점이 반대이므로 데이터 탐색이 많이 필요한 상황에서는 배열을 사용하고 데이터 삽입, 삭제가 많이 필요한 상황에서는 LinkedList를 사용하는 것이 효율적이다.

 

예를 들어, 리스트를 읽기만 할 때는 ArrayList가 압도적으로 좋지만 리스트의 추가, 삭제, 삽입을 한다면 LinkedList가 시간 복잡도 측면에서 더 좋은 경우가 있겠습니다.

 

LinkedList(연결리스트)의 종류

가. 단일 연결리스트(Singly LinkedList)

• 각 노드에 자료 공간과 한 개의 포인터 공간이 있고, 각 노드의 포인터는 다음 노드를 가리킨다.

나. 이중 연결리스트(Doubly LinkedList)

• 구조는 단일 연결리스트와 비슷하지만, 포인터 공간이 두 대가 있고 각각의 포인터는 앞의 노드와 뒤의 노드를 가리킨다.

다. 원형(환형) 연결리스트(Circular LinkedList)

• 일반적인 연결리스트에 마지막 노드와 처음 노드를 연결시켜 원형으로 만든 구조이다.

라. 이중 원형(환형) 연결리스트(Doubly Circular LinkedList)  

• 이중 연결리스트의 마지막 노드와 처음 노드를 연결시켜 원형으로 만든 구조이다.
•  

Reference

https://inpa.tistory.com/entry/JAVA-%E2%98%95-LinkedList-%EA%B5%AC%EC%A1%B0-%EC%82%AC%EC%9A%A9%EB%B2%95-%EC%99%84%EB%B2%BD-%EC%A0%95%EB%B3%B5%ED%95%98%EA%B8%B0

🧱 자바 LinkedList 구조 & 사용법 - 정복하기

https://hwan1001.tistory.com/5

[JAVA] 자료구조 클래스 - LinkedList(연결리스트)

https://cdragon.tistory.com/entry/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-LinkedList%EC%97%B0%EA%B2%B0-%EB%A6%AC%EC%8A%A4%ED%8A%B8

[자료구조 | Java] LinkedList(연결 리스트) 이론 및 구현