리스트
리스트
리스트란 순서를 가진 데이터들을 일자로 나열한 자료구조이다. 리스트의 종류에는 선형 리스트와 연결 리스트가 있다.
리스트 ADT
| element E |
| add(int idx, E e) | idx 위치에 데이터를 추가한다. |
| addFirst(E e) | 리스트의 맨 처음에 데이터를 추가한다. |
| addLast(E e) | 리스트의 맨 끝에 데이터를 추가한다. |
| get(int idx) | idx 위치의 데이터를 반환한다. |
| getFirst() | 리스트의 맨 처음의 데이터를 반환한다. |
| getLast() | 리스트의 맨 끝의 데이터를 반환한다. |
| set(int idx, E e) | idx 위치의 데이터를 e로 대체한다. |
| remove(int idx) | idx 위치의 데이터를 삭제한다. |
| clear() | 리스트의 모든 데이터를 제거한다. |
| size() | 리스트의 크기를 반환한다. |
| isEmpty() | 리스트가 비어있는지 검사한다. |
| printList() | 리스트 전체의 데이터를 출력한다. |
리스트 인터페이스
1
2
3
4
5
6
7
8
9
10
11
12
13
14
interface ListInterface<E> {
void add(int idx, E e);
void addFirst(E e);
void addLast(E e);
E get(int idx);
E getFirst();
E getLast();
void set(int idx, E e);
void remove(int idx);
void clear();
int size();
boolean isEmpty();
void printList();
}
선형 리스트
선형 리스트는 데이터의 논리적인 순서와 메모리의 저장된 물리적인 순서가 동일한 리스트다.
장점
배열로 구현하기 때문에 구현이 비교적 간단하다. 인덱스를 통해 데이터를 탐색하기 때문에 빠르다. O(1)의 시간복잡도를 가진다.
단점
삽입, 삭제 연산을 할 때마다 뒤에 저장된 데이터들을 밀거나 당겨야 하기 때문에 느리다. O(N)의 시간복잡도를 가진다. 리스트를 생성하는 시점에 크기가 결정된다. 따라서 리스트의 크기가 고정된다.
선형 리스트의 삽입 연산
add(int index, E e)의 작동 방식이다. index의 원소와 index 뒤의 원소들을 뒤로 한 칸씩 밀고 index 위치에 e를 삽입하면 된다.
선형 리스트의 삭제 연산
삭제 연산은 삽입 연산의 반대로 수행하면 된다. 삭제하려고 하는 원소보다 뒤에 있는 원소들을 앞으로 한 칸씩 당기면 된다.
선형 리스트 구현
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
class ArrayList<E> implements ListInterface<E> {
private static final int MAXSIZE = 100;
private E[] data = (E[]) new Object[MAXSIZE];
private int lastIdx = 0; // 원소를 저장할 수 있는 가장 마지막 인덱스
@Override
public void add(int idx, E e) {
if(idx < 0 || idx > lastIdx) {
throw new ArrayIndexOutOfBoundsException();
}
else {
for(int i = lastIdx - 1; i >= idx; i--) {
data[i + 1] = data[i];
}
lastIdx++;
data[idx] = e;
}
}
@Override
public void addFirst(E e) {
if(lastIdx == MAXSIZE) {
throw new ArrayIndexOutOfBoundsException();
}
else {
for(int i = lastIdx - 1; i >= 0; i--) {
data[i + 1] = data[i];
}
lastIdx++;
data[0] = e;
}
}
@Override
public void addLast(E e) {
if(lastIdx == MAXSIZE) {
throw new ArrayIndexOutOfBoundsException();
}
else {
data[lastIdx++] = e;
}
}
@Override
public E get(int idx) {
if(idx < 0 || idx >= lastIdx) {
throw new ArrayIndexOutOfBoundsException();
}
else {
return data
[idx];
}
}
@Override
public E getFirst() {
if(lastIdx == 0) {
throw new ArrayIndexOutOfBoundsException();
}
else {
return data[0];
}
}
@Override
public E getLast() {
if(lastIdx == 0) {
throw new ArrayIndexOutOfBoundsException();
}
else {
return data[lastIdx - 1];
}
}
@Override
public void set(int idx, E e) {
if(idx < 0 || idx >= lastIdx) {
throw new ArrayIndexOutOfBoundsException();
}
else {
data[idx] = e;
}
}
@Override
public void remove(int idx) {
if(idx < 0 || idx >= lastIdx) {
throw new ArrayIndexOutOfBoundsException();
}
else {
for(int i = idx; i < lastIdx - 1; i++) {
data[i] = data[i + 1];
}
lastIdx--;
}
}
@Override
public void clear() {
data = (E[]) new Object[MAXSIZE];
lastIdx = 0;
}
@Override
public int size() {
return lastIdx;
}
@Override
public boolean isEmpty() {
if(lastIdx == 0) {
return true;
}
else {
return false;
}
}
@Override
public void printList() {
for(int i = 0; i < lastIdx; i++) {
System.out.print(arr[i] + " ");
}
}
}
연결 리스트
연결 리스트는 각 노드가 데이터와 포인터(다른 노드에 대한 주소)를 가진 리스트이다. 연결 리스트의 종류에는 단순 연결 리스트, 원형 연결 리스트, 이중 연결 리스트가 있다.
장점
앞뒤의 링크만 끊고 이어주면 되므로 삽입, 삭제가 간단하다. 시간 복잡도는 O(1)이다. 리스트의 크기가 가변적이다.
단점
앞의 노드들을 전부 거쳐야 하므로 탐색이 비효율적이다. 시간복잡도는 O(N)이다.
연결 리스트의 삽입 연산
삽입하려는 노드를 curNode, curNode의 이전 노드를 prevNode라고 할 때, 연산은 다음과 같다.
- prevNode의 next를 curNode의 next에 대입한다.
- curNode를 prevNode의 next에 대입한다.
삽입하려는 노드가 첫 번째 혹은 마지막 노드일 때 head, tail 값에 유의하며 구현하면 된다. 단순 연결 리스트뿐만 아니라 원형, 이중 연결 리스트에서도 원리는 동일하다.
연결 리스트의 삭제 연산
삭제하려는 노드를 curNode, curNode의 이전 노드를 prevNode라고 할 때, 연산은 다음과 같다.
- curNode의 next를 prevNode의 next에 대입한다.
삭제하려는 노드가 첫 번째 혹은 마지막 노드일때 head, tail 값에 유의하며 구현하면 된다. 단순 연결 리스트뿐만 아니라 원형, 이중 연결 리스트에서도 원리는 동일하다.
단순 연결 리스트
단순 연결 리스트는 하나의 방향으로만 연결되어 있는 연결 리스트이다. head는 첫 번째 노드를, tail은 마지막 노드를 참조한다. 마지막 노드의 next는 null을 가리킨다.
단순 연결 리스트 구현
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
class SinglelyLinkedList<E> implements ListInterface<E> {
private Node<E> head = null;
private Node<E> tail = null;
private int listSize = 0;
private class Node<E> {
E data;
Node<E> next;
private Node(E data) {
this.data = data;
this.next = null;
}
}
private Node<E> findNode(int idx) {
Node<E> curNode = head;
for(int i = 0; i < idx; i++) {
curNode = curNode.next;
}
return curNode;
}
@Override
public void add(int idx, E e) {
if(idx < 0 || idx > listSize) {
throw new NullPointerException();
}
else if(idx == 0) {
addFirst(e);
}
else if(idx == listSize) {
addLast(e);
}
else {
Node<E> curNode = new Node<>(e);
Node<E> prevNode = findNode(idx);
curNode.next = prevNode.next;
prevNode.next = curNode;
listSize++;
}
}
@Override
public void addFirst(E e) {
Node<E> node = new Node<>(e);
node.next = head;
head = node;
listSize++;
if(listSize == 1) {
tail = node;
}
}
@Override
public void addLast(E e) {
Node<E> node = new Node<>(e);
if(listSize == 0) {
head = node;
}
else {
tail.next = node;
}
tail = node;
node.next = null;
listSize++;
}
@Override
public E get(int idx) {
if(idx < 0 || idx >= listSize) {
throw new NullPointerException();
}
else {
return findNode(idx).data;
}
}
@Override
public E getFirst() {
if(listSize == 0) {
throw new NullPointerException();
}
else {
return head.data;
}
}
@Override
public E getLast() {
if(listSize == 0) {
throw new NullPointerException();
}
else {
return tail.data;
}
}
@Override
public void set(int idx, E e) {
if(idx < 0 || idx >= listSize) {
throw new NullPointerException();
}
else if(idx == 0) {
head.data = e;
}
else if(idx == listSize - 1) {
tail.data = e;
}
else {
Node<E> node = findNode(idx);
node.data = e;
}
}
@Override
public void remove(int idx) {
if(idx < 0 || idx >= listSize) {
throw new NullPointerException();
}
else if(idx == 0) {
head = head.next;
if(listSize == 1) {
tail = null;
}
}
else if(idx == listSize - 1) {
Node<E> prevNode = findNode(idx - 1);
tail = prevNode;
prevNode.next = null;
}
else {
Node<E> prevNode = findNode(idx - 1);
Node<E> curNode = prevNode.next;
prevNode.next = curNode.next;
}
listSize--;
}
@Override
public void clear() {
head = null;
listSize = 0;
}
@Override
public int size() {
return listSize;
}
@Override
public boolean isEmpty() {
if(listSize == 0) {
return true;
}
else {
return false;
}
}
@Override
public void printList() {
Node<E> node = head;
for(int i = 0; i < listSize; i++) {
System.out.print(node.data + " ");
node = node.next;
}
}
}
원형 연결 리스트
원형 연결 리스트는 마지막 노드의 next가 첫 번째 노드를 가리키는 리스트이다. 단순 연결 리스트와 다르게 head가 마지막 노드를 참조하고, head.next가 첫 번째 노드를 참조한다. head가 첫 번째 노드를 참조하면 마지막 노드를 탐색하는 연산이 O(N)의 시간 복잡도를 가지지만, head가 마지막 노드를 참조하는 경우 O(1)의 시간 복잡도를 가진다.
원형 연결 리스트 구현
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
class CircularLinkedList<E> implements ListInterface<E> {
private Node<E> head = null;
private int listSize = 0;
private class Node<E> {
E data;
Node<E> next;
private Node(E data) {
this.data = data;
this.next = null;
}
}
private Node<E> findNode(int idx) {
Node<E> curNode = head.next;
for(int i = 0; i < idx; i++) {
curNode = curNode.next;
}
return curNode;
}
@Override
public void add(int idx, E e) {
if(idx < 0 || idx > listSize) {
throw new NullPointerException();
}
else if(idx == 0) {
addFirst(e);
}
else if(idx == listSize) {
addLast(e);
}
else {
Node<E> curNode = new Node<>(e);
Node<E> prevNode = findNode(idx);
curNode.next = prevNode.next;
prevNode.next = curNode;
listSize++;
}
}
@Override
public void addFirst(E e) {
Node<E> node = new Node<>(e);
if(listSize == 0) {
head = node;
node.next = head;
}
else {
node.next = head.next;
head.next = node;
}
listSize++;
}
@Override
public void addLast(E e) {
Node<E> node = new Node<>(e);
if(listSize == 0) {
head = node;
node.next = head;
}
else {
node.next = head.next;
head.next = node;
head = node;
}
listSize++;
}
@Override
public E get(int idx) {
if(idx < 0 || idx >= listSize) {
throw new NullPointerException();
}
else {
return findNode(idx).data;
}
}
@Override
public E getFirst() {
if(listSize == 0) {
throw new NullPointerException();
}
else {
return head.next.data;
}
}
@Override
public E getLast() {
if(listSize == 0) {
throw new NullPointerException();
}
else {
return head.data;
}
}
@Override
public void set(int idx, E e) {
if(idx < 0 || idx >= listSize) {
throw new NullPointerException();
}
else if(idx == 0) {
head.next.data = e;
}
else if(idx == listSize - 1) {
head.data = e;
}
else {
Node<E> node = findNode(idx);
node.data = e;
}
}
@Override
public void remove(int idx) {
if(idx < 0 || idx >= listSize) {
throw new NullPointerException();
}
else if(idx == 0) {
head.next = head.next.next;
}
else {
Node<E> prevNode = findNode(idx - 1);
Node<E> curNode = prevNode.next;
prevNode.next = curNode.next;
}
listSize--;
}
@Override
public void clear() {
head = null;
listSize = 0;
}
@Override
public int size() {
return listSize;
}
@Override
public boolean isEmpty() {
if(listSize == 0) {
return true;
}
else {
return false;
}
}
@Override
public void printList() {
if(listSize == 0) {
throw new NullPointerException();
}
Node<E> node = head.next;
for(int i = 0; i < listSize; i++) {
System.out.print(node.data + " ");
node = node.next;
}
}
}
이중 연결 리스트
이중 연결 리스트는 각 노드가 선행, 후행 노드에 대한 두 개의 주소를 가지는 리스트이다. 후행 노드를 찾기 힘들었던 다른 리스트와는 다르게 쉽게 후행 노드를 찾을 수 있다. 빨간색으로 표시된 노드는 헤드 노드이다. 리스트의 첫 번째 노드를 참조하던 헤드 포인터와는 다르게 삽입, 삭제 연산을 쉽게 하기 위해 존재한다.
이중 연결 리스트 구현
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
class DoublelyLinkedList<E> implements ListInterface<E> {
private Node<E> headNode;
private int listSize = 0;
private class Node<E> {
E data;
Node<E> next;
Node<E> prev;
private Node(E data) {
this.data = data;
this.next = null;
this.prev = null;
}
}
DoublelyLinkedList() {
headNode = new Node<>(null);
headNode.next = headNode;
headNode.prev = headNode;
}
private Node<E> findNode(int idx) {
Node<E> curNode = headNode.next;
for(int i = 0; i < idx; i++) {
curNode = curNode.next;
}
return curNode;
}
@Override
public void add(int idx, E e) {
if(idx < 0 || idx > listSize) {
throw new NullPointerException();
}
else if(idx == 0) {
addFirst(e);
}
else if(idx == listSize) {
addLast(e);
}
else {
Node<E> nextNode = findNode(idx);
Node<E> curNode = new Node<>(e);
Node<E> prevNode = nextNode.prev;
curNode.prev = prevNode;
curNode.next = nextNode;
prevNode.next = curNode;
nextNode.prev = curNode;
listSize++;
}
}
@Override
public void addFirst(E e) {
Node<E> node = new Node<>(e);
node.next = headNode.next;
node.prev = headNode;
headNode.next = node;
node.next.prev = node;
listSize++;
}
@Override
public void addLast(E e) {
Node<E> node = new Node<>(e);
node.prev = headNode.prev;
node.next = headNode;
node.prev.next = node;
headNode.prev = node;
listSize++;
}
@Override
public E get(int idx) {
if(idx < 0 || idx >= listSize) {
throw new NullPointerException();
}
else {
return findNode(idx).data;
}
}
@Override
public E getFirst() {
if(listSize == 0) {
throw new NullPointerException();
}
else {
return headNode.next.data;
}
}
@Override
public E getLast() {
if(listSize == 0) {
throw new NullPointerException();
}
else {
return headNode.prev.data;
}
}
@Override
public void set(int idx, E e) {
if(idx < 0 || idx >= listSize) {
throw new NullPointerException();
}
else if(idx == 0) {
headNode.next.data = e;
}
else if(idx == listSize - 1) {
headNode.prev.data = e;
}
else {
Node<E> node = findNode(idx);
node.data = e;
}
}
@Override
public void remove(int idx) {
if(idx < 0 || idx >= listSize) {
throw new NullPointerException();
}
else {
Node<E> curNode = findNode(idx);
curNode.prev.next = curNode.next;
curNode.next.prev = curNode.prev;
}
listSize--;
}
@Override
public void clear() {
headNode = new Node<>(null);
headNode.next = headNode;
headNode.prev = headNode;
listSize = 0;
}
@Override
public int size() {
return listSize;
}
@Override
public boolean isEmpty() {
if(listSize == 0) {
return true;
}
else {
return false;
}
}
@Override
public void printList() {
Node<E> node = headNode.next;
for(int i = 0; i < listSize; i++) {
System.out.print(node.data + " ");
node = node.next;
}
}
}
컬렉션 프레임워크
ArrayList
길이가 가변적인 선형 리스트이다. C++에서의 vector와 같다고 생각하면 된다. ArrayList 객체를 생성할 때 매개변수로 리스트의 크기를 정할 수 있다. 매개변수가 없으면 리스트의 기본 크기는 10이 된다. 리스트가 다 찼을 때 add() 메소드를 실행하면 grow() 메소드를 실행해서 리스트의 크기를 늘리는데, 이 과정에서 원래 리스트의 원소들을 전부 복사하므로 굉장히 비효율적이다.
LinkedList
This post is licensed under CC BY 4.0 by the author.