🔗 Node와 연결
연결 리스트에 들어가기 전에, 노드와 연결하는 컨셉에 대해 이해해야 한다. 일단 이전에 봤던 ArrayList는 내부에 배열을 사용해서 데이터를 보관하고 관리했다. 알다시피 배열은 크기를 미리 설정해야 하므로, 데이터가 어느 정도로 추가되는지 알 수 없는 상황의 경우, 공간이 낭비될 우려가 있었다. 그리고 배열의 앞이나 중간 위치에 데이터를 추가하려고 한다면, 나머지 데이터들을 옆으로 옮겨야 했다. 삭제의 경우에도 마찬가지다. 이런 식으로 ArrayList는 앞이나 중간 위치에 데이터를 추가/삭제를 하는 경우, 성능이 좋지 않다.
그래서 낭비되는 공간 없이 딱 필요한 만큼만 메모리를 확보해서 사용하고, 앞이나 중간 위치에 데이터를 추가/삭제하는 경우에도 효율적인 자료 구조가 필요했다. 여기서 “노드들을 만들고, 각 노드들을 연결” 하는 방식이 등장한다.
<Node 클래스>
public class Node {
Object item;
Node next;
}Node 클래스는 노드 내부에 "저장할 데이터(item)" 와 "다음 노드의 참조(next)" 로 구성되어 있다. 간단하게 이 Node 클래스를 사용해서 데이터 A, B, C를 순서대로 연결해보도록 하자.
- 일단 노드(
0번 노드)를 하나 만들어서item에A를 넣는다. - 노드 하나(
1번 노드)를 더 만들어서item에B를 넣고,0번 노드의next에1번 노드의 참조값을 넣어준다. (이로써0번 노드와1번 노드는 연결되었다.) - 노드(
2번 노드)를 하나 더 만들고item에C를 집어 넣는다.1번 노드의next에2번 노드의 참조값을 넣는다. (이로써1번 노드와2번 노드는 연결되었다.)
실제 코드로 구현해보면…
package collection.link;
public class Node {
Object item;
Node next;
public Node(Object item) {
this.item = item;
}
}package collection.link;
public class NodeMain1 {
public static void main(String[] args) {
// 노드 생성 후 연결: A -> B -> C
Node first = new Node("A"); // first에는 첫 번째 노드의 참조를 보관
first.next = new Node("B"); // 첫 번째 노드의 next에 두 번째 노드의 참조값을 보관
first.next.next = new Node("C"); // 두 번째 노드의 next에 세 번째 노드의 참조값을 보관
System.out.println("모든 노드 탐색하기");
Node x = first; // 처음에는 x에 첫 번째 노드의 참조가 들어 있음.
while (x != null) { // 참조값이 들어 있을 동안은...
System.out.println(x.item);
x = x.next; // x를 다음 노드의 참조값으로 업데이트
}
}
}
/*
모든 노드 탐색하기
A
B
C
*/그리고 데이터와의 연결 구조를 한눈에 볼 수 있도록 toString() 메서드를 오버라이딩해서 구현했다.
package collection.link;
public class Node {
Object item;
Node next;
public Node(Object item) {
this.item = item;
}
// [A -> B -> C] 형식으로 출력하고 싶다.
@Override
public String toString() {
// 반복문 안에서 문자를 더하기 때문에 StringBuilder 사용
StringBuilder sb = new StringBuilder();
Node x = this;
sb.append("[");
while (x != null) {
sb.append(x.item);
if (x.next != null) {
sb.append(" -> ");
}
x = x.next;
}
sb.append("]");
return sb.toString();
}
}연결된 노드 출력하기
[A -> B -> C]
보다시피 노드의 연결 구조를 아주 깔끔하게 볼 수 있다. 이제 노드와 연결을 활용해서 모든 노드를 탐색하는 기능, 마지막 노드를 조회하는 기능, 특정 인덱스의 노드를 조회하는 기능, 노드에 데이터를 추가하는 기능을 직접 구현해봄으로써 학습해보자.
package collection.link;
public class NodeMain3 {
public static void main(String[] args) {
// 노드 생성하고 연결하기: A -> B -> C
Node first = new Node("A");
first.next = new Node("B");
first.next.next = new Node("C");
System.out.println(first);
// 모든 노드 탐색하기
System.out.println("연결된 노드 출력하기");
printAll(first);
// 마지막 노드 반환하기
Node lastNode = getLastNode(first);
System.out.println(lastNode);
// 특정 index의 노드 조회하기
int index = 2;
Node index2Node = getNode(first, index);
System.out.println("index2Node = " + index2Node.item);
// 데이터 추가하기
System.out.println("=== 데이터 추가하기 ===");
add(first, "D");
System.out.println(first);
add(first, "E");
System.out.println(first);
add(first, "F");
System.out.println(first);
}
// 마지막 노드 조회 메서드 구현
private static Node getLastNode(Node node) {
Node x = node;
while (x.next != null) { // x.next의 참조값이 null이면 노드의 끝
x = x.next;
}
return x;
}
// 모든 노드를 탐색하는 메서드 구현
private static void printAll(Node node) {
Node x = node;
while (x != null) {
System.out.println(x.item);
x = x.next;
}
}
// 특정 인덱스의 노드를 조회하는 메서드 구현
private static Node getNode(Node node, int index) {
Node x = node;
for (int i = 0; i < index; i++) {
x = x.next;
}
return x;
}
// 특정 데이터를 추가하는 메서드 구현
private static void add(Node node, Object param) {
Node lastNode = getLastNode(node);
lastNode.next = new Node(param);
}
}
/*
[A -> B -> C]
연결된 노드 출력하기
A
B
C
[C]
index2Node = C
=== 데이터 추가하기 ===
[A -> B -> C -> D]
[A -> B -> C -> D -> E]
[A -> B -> C -> D -> E -> F]
*/
정리하자면, 노드는 내부에 데이터와 다음 노드에 대한 참조값을 가지고 있다. 각각의 노드가 그 참조값을 통해 연결(Link)되는 것이다. 데이터를 추가하고 싶을 때는 동적으로 필요한 만큼의 노드를 만들어서 연결하면 끝이다. 따라서 배열과는 다르게 메모리가 낭비되지 않는다. 이제 이런 식으로 “각각의 노드를 연결” 해서 사용하는 자료 구조를 사용해서 “연결 리스트(LinkedList)” 를 만들어 보도록 하자.
⛓ 연결 리스트(LinkedList)
List 자료 구조를 사용한다면, ArrayList를 사용하든 LinkedList를 사용하든 그냥 “순서가 있고, 중복을 허용하나보다…” 라고 이해하면 된다. 하여간, LinkedList는 기본적인 느낌은 ArrayList와 비슷하지만, 노드와의 연결 구조를 이용했다는 것이 포인트다. 코드로 구현해보자.
package collection.link;
public class MyLinkedListV1 {
private Node first; // 첫 노드의 위치
private int size = 0; // 자료 구조에 입력된 데이터의 사이즈
// 새로운 노드를 만들어서 마지막 노드에 연결
public void add(Object e) {
Node newNode = new Node(e); // 새로운 노드를 만들어서...
if (first == null) {
first = newNode;
} else {
Node lastNode = getLastNode(); // 마지막 노드의 위치를 찾아서
lastNode.next = newNode; // 새로운 노드를 마지막에 연결한다.
}
// 입력된 자료 구조의 사이즈 증가
size++;
}
// 마지막 노드를 찾아서 반환하는 메서드
private Node getLastNode() {
Node x = first;
while (x.next != null) {
x = x.next;
}
return x;
}
// 특정 위치의 노드를 찾아서 안의 데이터를 변경하는 메서드
public Object set(int index, Object element) {
Node x = getNode(index);
Object oldValue = x.item;
x.item = element;
return oldValue;
}
// 특정 위치에 있는 노드의 데이터를 반환하는 메서드
public Object get(int index) {
Node node = getNode(index);
return node.item;
}
// 특정 위치에 있는 노드를 반환하는 메서드
private Node getNode(int index) {
Node x = first;
for (int i = 0; i < index; i++) {
x = x.next;
}
return x;
}
// 특정 값이 몇 번째 인덱스에 있는지 찾아서 반환하는 메서드
public int indexOf(Object o) {
int index = 0;
for (Node x = first; x != null; x = x.next) {
if (o.equals(x.item)) {
return index;
}
index++;
}
// 없으면 -1 반환
return -1;
}
public int size() {
return size;
}
@Override
public String toString() {
return "MyLinkedListV1{" +
"first=" + first +
", size=" + size +
'}';
}
}package collection.link;
public class MyLinkedListV1Main {
public static void main(String[] args) {
MyLinkedListV1 list = new MyLinkedListV1();
System.out.println("=== 데이터 추가 ===");
System.out.println(list);
list.add("a");
System.out.println(list);
list.add("b");
System.out.println(list);
list.add("c");
System.out.println(list);
System.out.println("=== 기능 사용 ===");
System.out.println("list.size() = " + list.size());
System.out.println("list.get(1) = " + list.get(1));
System.out.println("list.indexOf('c') = " + list.indexOf("c"));
System.out.println("list.set(2, 'z') = " + list.set(2, "z"));
System.out.println(list);
System.out.println("=== 범위 초과 ===");
list.add("d");
System.out.println(list);
list.add("e");
System.out.println(list);
list.add("f");
System.out.println(list);
}
}
/*
=== 데이터 추가 ===
MyLinkedListV1{first=null, size=0}
MyLinkedListV1{first=[a], size=1}
MyLinkedListV1{first=[a -> b], size=2}
MyLinkedListV1{first=[a -> b -> c], size=3}
=== 기능 사용 ===
list.size() = 3
list.get(1) = b
list.indexOf('c') = 2
list.set(2, 'z') = c
MyLinkedListV1{first=[a -> b -> z], size=3}
=== 범위 초과 ===
MyLinkedListV1{first=[a -> b -> z -> d], size=4}
MyLinkedListV1{first=[a -> b -> z -> d -> e], size=5}
MyLinkedListV1{first=[a -> b -> z -> d -> e -> f], size=6}
*/기존의 MyArrayListV1Main에 있는 코드를 단지 MyLinkedListV1 list = new MyLinkedListV1()로만 변경해서 실행했다. 보다시피, LinkedList는 데이터를 추가할 때마다 동적으로 노드가 늘어나기 때문에 범위를 초과하는 문제가 발생하지 않고 잘 실행된다.
❓ LinkedList의 시간 복잡도
-
Object get(int index): 특정 위치에 있는 데이터를 반환하는 메서드다. 연결 리스트는 배열 리스트와는 다르게 노드들에 다음 노드에 대한 참조가 들어있다. 따라서 인덱스로 원하는 위치의 데이터를 찾으려면 인덱스 숫자 만큼 다음 노드를 계속해서 찾아야 한다. 따라서 특정 위치의 노드를 찾는데 O(n)이 걸린다. -
void add(Object e): 마지막에 데이터를 추가하는 메서드다. 알다시피 마지막 노드까지 계속 찾아가야 하므로 O(n)이 소요된다. 하지만 마지막까지 가면 그냥 새로운 노드를 추가하면 되기 때문에 O(1)이 걸린다. 따라서 최종으로 O(n)이 걸린다. -
Object set(int index, Object element): 특정 위치에 있는 데이터를 찾아서 변경하는 메서드로, 그 특정 위치까지 일단 찾아가야 한다. 따라서 O(n)이 걸린다. -
int indexOf(Object o): 데이터를 검색하고, 검색된 위치를 반환하는 메서드다. 모든 노드를 순회하면서 같은 값이 있는지 체크해야 하므로 O(n)이 걸린다.
🛠 특정 위치에 데이터 추가와 삭제 기능
기능을 구현하기 앞서, 어떤 식으로 구현해야 할지 생각해보자.
<첫 번째 위치에 추가하는 경우>
- 일단 추가할 노드를 생성한다.
- 그리고 새로 만든 노드와 그 노드 다음에 올 노드를 연결한다.
first를 추가된 노드의 참조값으로 대체한다.
이렇게 노드를 추가하면 오른쪽 노드의 인덱스가 하나씩 뒤로 밀린다. 여기서 이해를 위해 인덱스라고 한 것이지, 연결 리스트는 배열처럼 실제 인덱스가 존재하는 것은 아니다. 처음으로 연결된 노드를 0번 인덱스, 그 다음으로 연결된 노드를 1번 인덱스로 가정할 뿐이다.
LinkedList는 새로 생성한 노드의 참조만 변경하면 되므로 첫 번째 항목에 값을 추가하는 것은 O(1)로 매우 빠르다. 나머지 노드는 무슨 일이 일어난지 알 수 없다.
<첫 번째 위치의 데이터 삭제하는 경우>
- 일단 삭제 대상을 정한다.
first에 삭제 대상 노드의 다음 노드의 참조로 대체한다.
- 삭제 대상의 데이터를 초기화 해준다.
노드를 삭제하면 오른쪽 노드들의 인덱스가 하나씩 당겨져야 한다. 배열과 다르게 일부 참조만 변경하면 되므로, O(1)로 매우 빠르다. 나머지 노드는 어떤 일이 일어났는지 알 수 없다.
<중간 위치에 데이터를 추가하는 경우>
- 새로운 노드를 만들고, 노드를 추가할 위치의 직전 노드(
prev)를 찾는다.
- 새로 만든 노드를 다음 노드와 연결한다. 위의 그림에서는 1번 인덱스의 노드와 연결하는 것이다.
- 직전 노드(
prev)와 새로 만든 노드를 연결한다.
마찬가지로 노드를 추가했으므로 추가한 노드의 오른쪽에 있는 노드들의 인덱스를 하나씩 밀어야 한다. 노드를 추가할 위치를 찾는데 O(n)이 걸리고, 위치를 찾아서 노드를 추가하는 것은 O(1)이 걸려, 최종적으로 O(n)이 걸린다.
<중간 위치의 데이터를 삭제하는 경우>
- 삭제할 노드와 그 노드의 직전 노드를 찾는다.
- 직전 노드(
prev)의 다음 노드를 삭제 노드의 다음 노드와 연결한다.
- 삭제 노드의 데이터를 초기화한다.
노드를 삭제했으므로 삭제한 노드의 오른쪽 노드들의 인덱스는 하나씩 앞으로 당겨진다. 결과적으로 삭제할 노드를 찾는데 O(n), 찾은 노드를 삭제하는데 O(1)이 걸려서 최종적으로 O(n)이 걸린다.
이제 위의 기능들을 코드로 구현해보자.
package collection.link;
public class MyLinkedListV2 {
private Node first; // 첫 노드의 위치
private int size = 0; // 자료 구조에 입력된 데이터의 사이즈
// 새로운 노드를 만들어서 마지막 노드에 연결
public void add(Object e) {
Node newNode = new Node(e); // 새로운 노드 만들기
if (first == null) {
first = newNode;
} else {
Node lastNode = getLastNode(); // 마지막 노드의 위치를 찾아서
lastNode.next = newNode; // next에 새로운 노드의 위치를 대입
}
size++;
}
private Node getLastNode() {
Node x = first;
while (x.next != null) {
x = x.next;
}
return x;
}
// 추가 코드(특정 위치에 노드를 추가하는 메서드)
public void add(int index, Object e) {
Node newNode = new Node(e);
if (index == 0) {
newNode.next = first;
first = newNode;
} else {
Node prevNode = getNode(index - 1);
newNode.next = prevNode.next;
prevNode.next = newNode;
}
}
// 특정 위치의 노드를 찾아서 안의 데이터를 변경
public Object set(int index, Object element) {
Node x = getNode(index);
Object oldValue = x.item;
x.item = element;
return oldValue;
}
// 추가 코드
// 중간 위치의 데이터를 삭제하는 메서드
public Object remove(int index) {
Node removeNode = getNode(index); // 삭제하고 싶은 노드
Object removedItem = removeNode.item;
if (index == 0) {
first = removeNode.next;
} else {
getNode(index - 1).next = removeNode.next;
}
// 삭제할 노드를 초기화
removeNode.item = null;
removeNode.next = null;
size--;
return removedItem;
}
// 특정 위치에 있는 노드의 데이터를 반환
public Object get(int index) {
Node node = getNode(index);
return node.item;
}
private Node getNode(int index) {
Node x = first;
for (int i = 0; i < index; i++) {
x = x.next;
}
return x;
}
// 몇 번째 인덱스에 있는지 찾아서 반환
public int indexOf(Object o) {
int index = 0;
for (Node x = first; x != null; x = x.next) {
if (o.equals(x.item)) {
return index;
}
index++;
}
// 없으면 -1 반환
return -1;
}
public int size() {
return size;
}
@Override
public String toString() {
return "MyLinkedListV1{" +
"first=" + first +
", size=" + size +
'}';
}
}package collection.link;
public class MyLinkedListV2Main {
public static void main(String[] args) {
MyLinkedListV2 list = new MyLinkedListV2();
// 마지막에 추가 O(n)
list.add("a");
list.add("b");
list.add("c");
System.out.println(list);
// 첫 번째 항목에 추가 및 삭제
System.out.println("첫 번째 항목에 추가");
list.add(0, "d");
System.out.println(list);
System.out.println("첫 번째 항목을 삭제");
list.remove(0);
System.out.println(list);
// 중간 위치에 추가, 삭제
System.out.println("중간 위치에 추가");
list.add(1, "e");
System.out.println(list);
System.out.println("중간 위치에서의 삭제");
list.remove(1);
System.out.println(list);
}
}
/*
MyLinkedListV1{first=[a -> b -> c], size=3}
첫 번째 항목에 추가
MyLinkedListV1{first=[d -> a -> b -> c], size=3}
첫 번째 항목을 삭제
MyLinkedListV1{first=[a -> b -> c], size=2}
중간 위치에 추가
MyLinkedListV1{first=[a -> e -> b -> c], size=2}
중간 위치에서의 삭제
MyLinkedListV1{first=[a -> b -> c], size=1}
*/ArrayList와 LinkedList의 성능 비교
| 기능 | ArrayList | LinkedList |
|---|---|---|
| 인덱스 조회 | O(1) | O(n) |
| 검색 | O(n) | O(n) |
| 앞에 추가(삭제) | O(n) | O(1) |
| 뒤에 추가(삭제) | O(1) | O(n) |
| 중간 위치에 추가(삭제) | O(n) | O(n) |
데이터를 조회할 일이 많고, 뒷부분에 데이터를 추가해야 한다면 ArrayList가 더 좋은 성능을 제공하고, 앞쪽에 데이터를 추가하거나 삭제할 일이 많다면 LinkedList를 사용하는 것이 더 좋은 성능을 제공한다.
지금은 단일 연결 리스트만 구현했지만, 노드를 앞뒤로 모두 연결하는 이중 연결 리스트를 사용하면 성능을 더 개선시킬 수 있다. 참고로 자바가 제공하는 LinkedList는 “이중 연결 리스트” 다. 그리고 마지막 노드를 참조하는 변수를 가지고 있어서 뒤에 추가하거나 삭제하는 경우에도 O(1)의 성능을 제공한다.
🎭 제네릭 도입
LinkedList에 제네릭을 도입해서 타입 안전성도 높여보자.
package collection.link;
public class MyLinkedListV3<E> {
private Node<E> first; // 첫 노드의 위치
private int size = 0; // 자료 구조에 입력된 데이터의 사이즈
// 새로운 노드를 만들어서 마지막 노드에 연결
public void add(E e) {
Node<E> newNode = new Node(e); // 새로운 노드 만들기
if (first == null) {
first = newNode;
} else {
Node<E> lastNode = getLastNode(); // 마지막 노드의 위치를 찾아서
lastNode.next = newNode; // next에 새로운 노드의 위치를 대입
}
size++;
}
private Node<E> getLastNode() {
Node<E> x = first;
while (x.next != null) {
x = x.next;
}
return x;
}
public void add(int index, E e) {
Node<E> newNode = new Node<>(e);
if (index == 0) {
newNode.next = first;
first = newNode;
} else {
Node<E> prevNode = getNode(index - 1);
newNode.next = prevNode.next;
prevNode.next = newNode;
}
}
// 특정 위치의 노드를 찾아서 안의 데이터를 변경
public E set(int index, E element) {
Node<E> x = getNode(index);
E oldValue = x.item;
x.item = element;
return oldValue;
}
// 중간 위치의 데이터를 삭제하는 메서드
public E remove(int index) {
Node<E> removeNode = getNode(index); // 삭제하고 싶은 노드
E removedItem = removeNode.item;
if (index == 0) {
first = removeNode.next;
} else {
Node<E> prev = getNode(index - 1);
prev.next = removeNode.next;
}
// 삭제할 노드를 초기화
removeNode.item = null;
removeNode.next = null;
size--;
return removedItem;
}
// 특정 위치에 있는 노드의 데이터를 반환
public E get(int index) {
Node<E> node = getNode(index);
return node.item;
}
private Node<E> getNode(int index) {
Node<E> x = first;
for (int i = 0; i < index; i++) {
x = x.next;
}
return x;
}
// 몇 번째 인덱스에 있는지 찾아서 반환
public int indexOf(E o) {
int index = 0;
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item)) {
return index;
}
index++;
}
// 없으면 -1 반환
return -1;
}
public int size() {
return size;
}
@Override
public String toString() {
return "MyLinkedListV1{" +
"first=" + first +
", size=" + size +
'}';
}
// Node 클래스를 제네릭 타입으로 선언
private static class Node<E> {
E item; // Integer로 들어올지, String으로 들어올지 모르겠다!
Node<E> next;
public Node(E item) {
this.item = item;
}
// [A -> B -> C] 형식으로 출력하고 싶다.
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
Node<E> x = this;
sb.append("[");
while (x != null) {
sb.append(x.item);
if (x.next != null) {
sb.append(" -> ");
}
x = x.next;
}
sb.append("]");
return sb.toString();
}
}
}Object로 처리하던 부분을 타입 매개 변수(<E>)로 변경하고, 정적 중첩 클래스로 새로 선언한 Node<E>도 제네릭 타입으로 선언했다. 현재 Node 클래스는 MyLinkedList 안에서만 사용하고 있으므로, 중첩 클래스로 만든 것이다.
package collection.link;
public class MyLinkedListV3Main {
public static void main(String[] args) {
MyLinkedListV3<String> stringList = new MyLinkedListV3<>();
stringList.add("a");
stringList.add("b");
stringList.add("c");
String string = stringList.get(0);
System.out.println("string = " + string);
MyLinkedListV3<Integer> intList = new MyLinkedListV3<>();
intList.add(1);
intList.add(2);
intList.add(3);
Integer integer = intList.get(0);
System.out.println("integer = " + integer);
}
}
/*
string = a
integer = 1
*/