[CS - Data Structure] 연결 리스트 (Linked List) 구조 및 구현
LinkedList 구조
자바의 LinkedList는 ArrayList와 같이 인덱스로 접근하여 조회/삽입이 가능하지만 내부 구조는 완전히 다르게 구성되어 있다는 점이 특징이다.
ArrayList는 내부적으로 배열을 이용하여 메서드로 여기저기 조작이 가능하게 만든 컬렉션이라면,
LinkedList는 노드(객체) 끼리의 주소 포인터를 서로 가리키며 링크(참조)함으로써 이어지는 구조이다.
컬렉션 (Collection)
많은 데이터 요소를 효율적으로 관리하기 위한 자료구조를 말하며, ArrayList, LinkedList, HashMap 등이 여기에 포함된다.
LinkedList는 각 노드마다 화살표로 연결되어 선형 리스트 형태로 나열되어 있다.
여기서 노드는 하나의 객체이다. 즉, 객체를 만들면 객체의 주소가 생기고, 노드마다 각 객체의 주소를 서로 참조하면서 연결 형태를 구성한다.
각 노드는 데이터 필드와 다음 노드에 대한 참조를 포함하는 next 포인터 필드로 구성
단일 노드를 아래와 같이 작성할 수 있다.
1
2
3
4
class Node {
Node next; // 다음 노드 주소를 저장하는 필드
int data; // 데이터를 저장하는 필드
}
LinkedList 종류는 아래와 같다.
- 단방향 연결 리스트 (Singly LinkedList)
- 양방향 연결 리스트 (Doubly LinkedList)
- 양방향 원형 연결 리스트 (Doubly Circular LinkedList)
단방향 연결 리스트 (Singly LinkedList)
다음 노드를 가리키기 위한 포인터 필드 next만 가지고 있는 LinkedList를 Singly LinkedList라고 한다.
하지만 단일 연결 리스트는 현재 요소에서 이전 요소로 접근해야 할 때 매우 부적합한 특징이 있다. 예를 들어, LinkedList에 저장된 데이터가 10000개일 때 9999번째 데이터에 접근하려면 Node를 9999번 이동해야 한다.
이를 극복한 것이 Doubly LinkedList 구조이다.
양방향 연결 리스트 (Doubly LinkedList)
기존의 단일 연결 노드 객체에서 이전 노드 주소를 담고 있는 필드 prev가 추가된 형태를 Doubly LinkedList라고 부른다.
Singly LinkedList는 이동 방향이 단방향이기 때문에, 이를 보완하여 역순으로도 검색이 가능하도록 한 것이다.
따라서 Doubly LinkedList는 Singly LinkedList보다 각 요소에 대한 접근과 이동이 쉽기 때문에 기본적으로 많이 사용된다.
단일 노드를 아래와 같이 작성할 수 있다.
1
2
3
4
5
class Node {
Node next; // 다음 노드 주소를 저장하는 필드
Node prev; // 이전 노드 주소를 저장하는 필드
int data; // 데이터를 저장하는 필드
}
Java의 컬렉션 프레임워크에 구현된 LinkedList 클래스는 Doubly LinkedList로 구현되어 있다.
양방향 원형 연결 리스트 (Doubly Circular LinkedList)
Doubly Circular LinkedList는 Doubly LinkedList보다 접근성이 더 개선되었다.
단순히 첫번째 노드와 마지막 노드를 연결시켜서 원형 리스트처럼 만든 것이다.
이러한 구조는 TV 채널을 순회하거나, 오디오 플레이어와 같이 데이터를 순차적 방식으로 처리하다가 마지막 요소를 만나면 다시 처음 요소로 되돌아가는 애플리케이션에서 사용된다.
잘 쓰이지는 않는다.
LinkedList vs ArrayList
| LinkedList | ArrayList | |
|---|---|---|
| 컬렉션 구성 | 노드를 연결 | 배열을 이용 |
| 데이터 접근 시간 | 위치에 따라 이동시간 발생 | 모든 데이터 상수 시간 접근 |
| 삽입 / 삭제 시간 | 위치에 따라 그 위치까지 이동하는 시간 발생 | 데이터 이동이 필요한 경우 추가시간 발생 |
| 리사이징 필요 | - | 공간이 부족할 경우 새로운 배열에 복사하는 추가 시간 발생 |
| 데이터 검색 | 최악의 경우 리스트에 있는 아이템 수 만큼 확인 | |
| CPU Cache | - | 캐시 이점을 활용 |
시간복잡도
추가
원하는 노드를 하나 만들고, 그 노드와 Tail 노드의 next 포인터를 연결하는 작업이다.
마찬가지로 처음부터 끝까지 순회하면서 마지막 노드가 가리키고 있는 Null 위치에 원하는 노드를 추가시키는 개념이다.
ArrayList와는 달리, 마지막 노드를 찾지 않아도 되고, 그저 tail 노드에서 새로운 노드를 추가하는 것이기 때문에 시간 복잡도는 O(1)이다.삽입
LinkedList는 ArrayList와는 다르게 데이터를 뒤로 한 칸씩 전부 밀어줄 필요가 없다.
간단히 포인터만 바꿔주면 되기 때문에 논리는 간단하다.
하지만 삽입 위치를 찾기 위해서는 순회를 통해 찾아야하기 때문에 시간 복잡도는 O(N)이다.예를 들어, [A, C] 가운데에 B를 삽입할 경우 B노드의 이전인 A노드의 next 포인터를 본인 B노드와 연결하고,
이전 A노드의 next 포인터가 가리키고 있던 C노드를 본인 B노드의 next 포인터로 가리키게 한다.삭제
LinkedList에서 삭제하고자 하는 노드가 있을 때 head와 tail 노드로 무작정 알아낼 수 없기 때문에 그 위치를 찾아가는 시간 복잡도는 O(N)이다.
ArrayList에서는 삭제할 위치를 찾고 뒤의 데이터들을 앞으로 한 칸씩 당기는데 시간이 O(N)만큼 또 소요가 됐다면,
LinkedList는 데이터를 당겨오지 않고 포인터만 조금 바꿔주면 삭제 과정이 자동으로 이루어진다.예를 들어, [A, B, C]에서 B를 삭제할 경우 B노드의 이전인 A노드의 next 포인터는 삭제할 B노드의 next 포인터가 가리키고 있던 C노드를 가리키게 되고,
삭제할 B노드의 next 포인터는 아무것도 가리키지 않는 상태인 null 상태가 되게 한다.
그 이후 자바에서는 GC에 의해 붕떠 있던 삭제 노드는 알아서 사라지게 된다.검색
LinkedList에서 검색은 ArrayList의 검색과 마찬가지로,
head 노드에서부터 tail 노드까지 순차적으로 순회하면서 데이터를 찾아가기 때문에 시간 복잡도는 O(N)이다.
ArrayList는 대신 index로 검색을 하는 경우 Random Access(임의 접근 방식)가 가능하여 데이터를 처음부터 찾을 필요가 없기 때문에 시간 복잡도는 O(1)이다.
| LinkedList | ArrayList | |
|---|---|---|
| 추가 | O(1) | O(1), O(N) |
| 삽입 | O(N) | O(N) |
| 삭제 | O(N) | O(N) |
| 검색 | O(N) | O(1) |
LinkedList 장단점
- 장점
- 배열의 복사나 재할당 없이 데이터 추가가 가능하고, 유연한 공간을 갖는다.
ArrayList는 배열이 꽉 차있는 경우 크기를 늘려 준 다음 데이터를 다시 추가해 주는 과정을 진행해야 하는데
LinkedList는 쓰는 공간만큼만 크기가 늘었다 줄었다 하기 때문에 메모리 측면에서 훨씬 효율적이다.
- 배열의 복사나 재할당 없이 데이터 추가가 가능하고, 유연한 공간을 갖는다.
- 단점
- 데이터 접근에 대한 시간이 늘어난다.
ArrayList와는 달리, index로 검색하는 Random Access가 되지 않기 때문에 원하는 노드를 찾아야 하는 경우 O(N)의 시간 복잡도가 발생한다.
- 데이터 접근에 대한 시간이 늘어난다.
리스트를 읽기만 할 때는 ArrayList가 좋지만,
추가, 삭제, 삽입을 한다면 LinkedList 사용이 더 좋을 수 있을 것 같다.
LinkedList 구현
list interface 코드 작성
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public interface IList<T> {
void add(T t);
void insert(int index, T t);
void clear();
boolean delete(T t);
boolean deleteByIndex(int index);
T get(int index);
int indexOf(T t);
boolean isEmpty();
boolean contains(T t);
int size();
}
List의 기능을 확인할 각 메서드의 프로토타입들을 IList라는 인터페이스로 선언
LinkedList 구현
- add
- insert
- clear
- delete
- deleteByIndex
- get
- indexOf
- isEmpty
- contains
- size
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
public class MyLinkedList<T> implements IList<T> {
private int size;
private Node head;
public MyLinkedList() {
// 생성자에서 size와 head 노드를 초기화.
this.size = 0;
this.head = null; // dummy node
}
private class Node {
/*
LinkedList는 노드 기반이기 때문에 사용할 노드도 생성.
노드에는 데이터를 담기 위한 data필드와 다음 노드를 가리키기 위한 포인터 객체 next 생성.
인자를 data 하나만 받는 경우와 data, 포인터 객체 next 두 가지를 받는 경우에 맞게 초기화시켜주는 생성자 생성.
*/
T data;
Node next;
Node(T data) {
this.data = data;
}
Node(T data, Node next) {
this.data = data;
this.next = next;
}
}
@Override
public void add(T t) {
/*
curr이라는 노드는 순회를 위해서 현재 위치를 특정짓기 위한 노드이다.
head노드부터 시작해야 되기 때문에 head노드를 curr노드에 대입한다. (curr노드 진입)
순회는 null 이전까지 해야하기 때문에 while문에 조건을 붙여 반복해준다.
curr의 next 포인터를 curr로 지정하면서 계산 앞으로 순회가 된다.
반복문이 종료되면 LinkedList의 끝이므로 추가하고자 하는 노트를 새로 생성한다.
curr의 next 포인터가 새로 생성된 노드를 가리키게 하며, size는 1만큼 증가시킨다.
*/
Node curr = this.head;
while (curr != null) {
curr = curr.next;
}
Node node = new Node(t);
curr.next = node;
this.size++;
}
@Override
public void insert(int index, T t) {
/*
insert는 구현방식이 ArrayList와 크게 다르지 않다.
다만, ArrayList와 같이 뒤의 데이터를 전부 밀지 않고 포인터 몇 개만 조금 바꿔주면 된다.
먼저, prev노드는 head노드이기 때문에 curr 노드는 prev노드의 next 포인터가 가리키는 노드여야 한다.
삽입하고자 하는 index의 수만큼 순회를 진행하는데, 반복문이 진행됨에 따라 prev노드와 curr노드를 다음 노드로 계속해서 이동해 준다.
해당 index만큼 반복이 진행 되었을 때 prev 노드와 curr 노드는 삽입을 원하는 위치의 노드로 초기화된다.
그 이후 curr 노드를 인자로 하여 삽입하고자 하는 노드를 생성한다.
이때 생성하는 노드의 next 포인터가 가리키는 노드가 curr노드가 되도록 해준다.
prev노드의 next 포인터를 생성한 노드를 대입하고, 배열의 크기를 1 증가시킨다.
*/
if (index > this.size || index < 0) {
throw new IndexOutOfBoundsException();
}
Node prev = this.head;
Node curr = prev.next;
int i = 0;
while (i++ < index) {
prev = prev.next;
curr = curr.next;
}
Node node = new Node(t, curr);
prev.next = node;
this.size++;
}
@Override
public void clear() {
/*
ArrayList와는 다르게 LinkedList의 clear에서는 sizefmf 0으로 초기화 시켜주는 것 뿐 아니라 LinkedList의 모든 연결을 끊어줘야 한다.
따라서 head노드의 next 포인터가 가리키고 있는 객체를 null로 초기화 시켜주면 LinkedList의 clear 과정이 진행된다.
LinkedList를 타고 들어가는 방법은 오직 head노드를 통한 경로밖에 없다.
따라서 head노드와 다른 노드의 연결을 끊어주는 행위, 즉 null로 초기화 시키는 과정을 진행하면 자연스럽게 연결리스트가 초기화 된다.
*/
this.size = 0;
this.head.next = null;
}
@Override
public boolean delete(T t) {
/*
LinkedList에서의 삭제는 뒤의 데이터를 당겨주는 과정(시간 복잡도 O(N))없이 포인터 몇 개만 조금 바꿔주는 것으로 구현할 수 있다.
while문을 통해 노드를 순회하고 조건문을 통해 조건에 맞는 prev노드와 curr노드가 정해졌을 때
prev노드의 next 포인터가 가리키고 있는 것은 삭제하고자 하는 curr노드이기 때문에 curr노드의 next 포인터가 가리키고 있던 노드와 연결시킨다.
curr노드의 next 포인터는 아무것도 가리키지 않는 상태로 만들어 주기 위해 null로 초기화 시켜주고, 리스트의 크기를 1 감소시킨다.
*/
Node prev = this.head;
Node curr = prev.next;
while (curr != null) {
if (curr.data.equals(t)) {
prev.next = curr.next;
curr.next = null;
this.size--;
return true;
}
prev = prev.next;
curr = curr.next;
}
return false;
}
@Override
public boolean deleteByIndex(int index) {
/*
deleteByIndex는 index로 노드를 찾아 해당 노드를 삭제시키는 것이다.
따라서 인자로 받는 index의 범위가 음수이거나 리스트의 size보다 크거나 같은 경우 예외를 던진다.
prev노드와 curr노드를 초기화시키고 while문을 index까지 i를 증가시킨다. 이때 prev노드와 curr노드를 다음 노드로 이동하는 과정을 반복한다.
반복문이 종료된 시점에는 curr노드는 index만큼의 노드가 되고, prev노드는 그 이전의 노드가 되기 때문에 delete와 동일한 방법으로 삭제시킨다.
*/
if (index >= this.size || index < 0) {
throw new IndexOutOfBoundsException();
}
Node prev = this.head;
Node curr = prev.next;
int i = 0;
while (i++ < index) {
prev = prev.next;
curr = curr.next;
}
prev.next = curr.next;
curr.next = null;
this.size--;
return true;
}
@Override
public T get(int index) {
/*
get은 원하는 노드의 data만 얻고 싶은 것이기 때문에 prev노드는 사용하지 않는다.
curr노드를 생성하여 이를 원하는 index까지 이동시켜 그 노드의 data를 반환한다.
*/
if (index >= this.size || index < 0) {
throw new IndexOutOfBoundsException();
}
Node curr = this.head.next;
int i = 0;
while (i++ < index) {
curr = curr.next;
}
return curr.data;
}
@Override
public int indexOf(T t) {
/*
indexOf 메서드는 인자로 받아온 t와 일치하는 노드의 index를 반환하는 메서드이다.
curr노드를 생성하고 while 반복문을 통해 index를 0부터 증가시키면서 리스트의 끝까지 반복시키고 curr노드를 이동시켜 리스트를 순회한다.
그리고 현재 노드와 인자 t가 일치할 때 index를 반환한다.
*/
Node curr = this.head.next;
int index = 0;
while (curr != null) {
if (t.equals(curr.data)) {
return index;
}
curr = curr.next;
index++;
}
return -1;
}
@Override
public boolean isEmpty() {
/*
LinkedList는 head노드의 next 포인터가 가리키고 있는 노드가 null로 하여 연결리스트의 초기 상태로 리스트가 비어있는 것을 알 수 있다.
추가로 ArrayList의 isEmpty 메서드처럼 size가 0인 것으로 구현해도 된다.
*/
return this.head.next == null;
}
@Override
public boolean contains(T t) {
/*
ArrayList의 contains 메서드같이 반복문을 통해 하니씩 돌면서 equals 메서드로 리스트의 원소와 일치하면 true, 아니면 false를 반환한다.
*/
Node curr = this.head.next;
while (curr != null) {
if (t.equals(curr.data)) {
return true;
}
curr = curr.next;
}
return false;
}
@Override
public int size() {
/*
리스트의 크기를 반환할 때 반복문을 돌면서 tail노드까지 접근하면서 index를 증가시키는 방법도 있지만 시간복잡도 O(N)이 발생하므로 비효율적이다.
따라서 간단하게 this.size를 반환한다.
*/
return this.size;
}
}