- 연결 리스트는 배열 리스트의 단점인 메모리낭비, 중간위치의 데이터 추가에 대한 성능 문제를 어느정도 극복할 수 있음
리스트 자료 구조
-
순서가 있고, 중복을 허용하는 자료구조를 리스트라고 함
-
연결 리스트도 앞서 구현한
MyArrayList처럼 모두 같은 리스트임 -
리스트의 내부에서 배열을 사용하는가 아니면 노드와 연결 구조를 사용하는가의 차이만 있을 뿐임
-
배열 리스트를 사용하든 연결 리스트를 사용하든 둘 다 리스트 자료구조이기 때문에, 리스트를 사용하는 개발자 입장에서는 거의 비슷하게 느껴져야 함
- 리스트를 사용하는 개발자의 입장에서
MyArrayList를 사용하든MyLinkedList를 사용하든 내부가 어떻게 돌아갈지는 몰라도, 그냥 순서가 있고 중복을 허용하는 자료 구조라고 생각하고 사용할 수 있어야 함
- 리스트를 사용하는 개발자의 입장에서
연결 리스트 구현 1
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++;
}
return -1;
}
public int size() {
return size;
}
@Override
public String toString() {
return "MyLinkedListV1{" +
"first=" + first +
", size=" + size +
'}';
}
}Node first: 첫 노드의 위치를 가리킴size: 자료 구조에 입력된 데이터의 사이즈, 데이터가 추가될 때마다 하나씩 증가함
void add(Object e)
public void add(Object e) {
Node newNode = new Node(e);
if (first == null) {
first = newNode;
}
else {
Node lastNode = getLastNode();
lastNode.next = newNode;
}
size++;
}- 마지막에 데이터를 추가함
- 새로운 노드를 만들고, 마지막 노드를 찾아서 새로운 노드를 마지막에 연결함
- 만약 노드가 하나도 없다면 새로운 노드를 만들고
first에 연결함
Object set(int index, Object element)
public Object set(int index, Object element) {
Node x = getNode(index);
Object oldValue = x.item;
x.item = element;
return oldValue;
}
private Node getNode(int index) {
Node x = first;
for (int i = 0; i < index; i++) {
x = x.next;
}
return x;
}- 특정 위치에 있는 데이터를 찾아서 변경함
- 그리고 기존 값을 반환
getNode(index)를 통해 특정 위치에 있는 노드를 찾고, 단순히 그 노드에 있는item데이터를 변경함
Object get(int index)
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;
}- 특정 위치에 있는 데이터를 반환함
getNode(index)를 통해 특정 위치에 있는 노드를 찾고, 해당 노드에 있는 값을 반환함
int indexOf(Object o)
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++;
}
return -1;
}- 데이터를 검색하고, 검색된 위치를 반환함
- 모든 노드를 순회하면서
equal()를 사용해서 같은 데이터가 있는지 찾음
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'), oldValue: " + 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);
}
}- MyArrayListV1Main에 있는 코드를 거의 그대로 사용
- MyArrayListV1 리스트와 제공하는 기능이 같기 때문에 메서드 이름도 동일하게 맞춤
- 연결리스트는 데이터를 추가할 때마다 동적으로 노드가 늘어나기 때문에, 범위를 초과하는 문제는 발생하지 않음
실행결과
==데이터 추가==
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'), oldValue: 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}연결 리스트와 빅오
Object get(int index)
- 특정 위치에 있는 데이터를 반환함
O(n)- 배열은 인덱스로 원하는 데이터를 즉시 찾을 수 있음
- 따라서 배열을 사용하는 배열 리스트도 인덱스로 조회시
O(1)의 빠른 성능을 보장함
- 따라서 배열을 사용하는 배열 리스트도 인덱스로 조회시
- 하지만 연결 리스트에서 사용하는 노드들은 배열이 아님
- 단지 다음 노드에 대한 참조만 있을 뿐이기 때문에, 인덱스로 원하는 위치의 데이터를 찾으려면 인덱스 숫자만큼 다음 노드를 반복해서 찾아야 함
- 따라서 인덱스 조회 성능이 나쁨
- 배열은 인덱스로 원하는 데이터를 즉시 찾을 수 있음
void add(Object e)
- 마지막에 데이터를 추가함
O(n)- 마지막 노드를 찾는데 O(n)이 소요됨
- 마지막 노드에 새로운 노드를 추가하는데 O(1)이 걸림
- 따라서 O(n)임
Object set(int index, Object element)
- 특정 위치에 있는 데이터를 찾아서 변경하고, 기존 값을 반환
O(n)- 특정 위치의 노드를 찾는데 O(n)이 걸림
int indexOf(Object o)
- 데이터를 검색하고, 검색된 위치를 반환함
O(n)- 모든 노드를 순회하면서
equal()를 사용해서 같은 데이터가 있는지 찾음
- 모든 노드를 순회하면서
정리
- 연결 리스트를 통해 데이터를 추가하는 방식은 꼭 필요한 메모리만 사용함
- 따라서 배열 리스트의 단점인 메모리 낭비를 해결할 수 있음
- 물론 연결을 유지하기 위한 추가 메모리가 사용되는 단점도 함께 존재함
연결 리스트 구현 2 - 추가와 삭제
- 특정 위치에 있는 데이터를 추가하고, 삭제하는 기능 구현
void add(int index, Object e)
- 특정 위치에 데이터를 추가함
- 내부에서 노드도 함께 추가됨
Object remove(int index)
- 특정 위치에 있는 데이터를 제거함
- 내부에서 노드도 함께 제거됨
첫번째 위치에 데이터 추가
첫 번째 항목에 "d"를 추가해서 [d->a->b->c]로 만드는 코드를 분석
- 신규 노드 생성
- 신규 노드와 다음 노드 연결
- first에 신규 노드 연결
- 최종결과
-
노드를 추가했으므로 오른쪽 노드의 index가 하나씩 뒤로 밀려남
- 연결 리스트는 배열처럼 실제 index가 존재하는 것이 아님
- 처음으로 연결된 노드를 index 0, 그 다음으로 연결된 노드를 index 1으로 가정할 뿐이고, 연결 리스트에서 index는 연결된 순서를 뜻함
-
배열의 경우 첫 번째 항목에 데이터가 추가되면 모든 데이터를 오른쪽으로 하나씩 밀어야하지만, 연결 리스트는 새로 생성한 노드의 참조만 변경하면 됨
- 나머지 노드는 어떤일이 일어난지도 모름
-
연결 리스트의 첫 번째 항목에 값을 추가하는 것은 매우 빠르게 O(1) 시간으로 표현할 수 있음
첫 번째 위치의 데이터 삭제
- 첫 번째 항목을 삭제하는 코드 분석
-
더는 삭제 노드를 참조하는 곳이 없음
- 이후 삭제 노드는 GC의 대상이 되어서 제거됨
-
노드를 삭제했으므로 오른쪽 노드의 index가 하나씩 당겨짐
-
연결 리스트는 일부 참조만 변경하면 됨
-
연결 리스트의 첫 번째 항목에 값을 삭제하는 것은 매우 빠른 O(1)으로 표현할 수 있음
중간 위치에 데이터 추기
- 중간 항목에 "e"를 추가하는 코드를 분석
-
새로운 노드를 생성하고 노드가 입력될 위치의 직전 노드(prev)를 찾아둔다.
-
신규 노드와 다음 노드를 연결한다. 직전 노드(prev)의 다음 노드를 연결하면 된다.
-
직전 노드(prev)에 신규 노드를 연결한다.
최종결과
- 노드를 추가했으므로 추가한 노드 오른쪽에 있는 노드들의 index가 하나씩 뒤로 밀려남
- 연결 리스트는 새로 생성한 노드의 참조만 변경하면 됨
- O(n)의 성능임
- 연결 리스트는 인덱스를 사용해서 노드를 추가할 위치를 찾는데 O(n)이 걸림
- 위치를 찾고 노드를 추가하는데는 O(1)이 걸림
- 따라서 둘을 합치면 O(n)이 걸림
중간 위치의 데이터 삭제
- O(n)의 성능
- 연결리스트에서 인덱스로 삭제할 항목을 찾는데 O(n)이 걸림
- 연결 리스트에서 항목을 삭제하는 것은 O(1)으로 매우 빠름
- 연결 리스트와 배열 리스트 둘 다 중간에 있는 항목을 추가하거나 삭제하는 경우 둘 다 같은 O(n)임
특정 위치에 있는 데이터를 추가하고 삭제하는 기능 코드 구현
//추가 코드
public void add(int index, Object e) {
Node newNode = new Node(e);
if (index == 0) {
newNode.next = first;
first = newNode;
}
else {
Node prev = getNode(index - 1);
newNode.next = prev.next;
prev.next = newNode;
}
size++;
}
//추가 코드
public Object remove(int index) {
Node removeNode = getNode(index);
Object removedItem = removeNode.item;
if (index == 0) {
first = removeNode.next;
}
else {
Node prev = getNode(index - 1);
prev.next = removeNode.next;
}
removeNode.item = null;
removeNode.next = null;
size--;
return removedItem;
}
void add(int index, Object e)
- 특정 위치에 데이터를 추가
- 내부에서 노드도 함께 추가
Object remove(int index)
- 특정 위치에 있는 데이터를 제거
- 내부에서 노드도 함께 제거
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"); //O(1)
System.out.println(list);
System.out.println("첫 번째 항목 삭제");
list.remove(0); //remove First O(1)
System.out.println(list);
//중간 항목에 추가, 삭제
System.out.println("중간 항목에 추가");
list.add(1,"e"); //O(n)
System.out.println(list);
System.out.println("중간 항목 삭제");
list.remove(1);//remove O(n)
System.out.println(list);
}
}실행 결과
MyLinkedListV2{first=[a->b->c], size=3}
첫 번째 항목에 추가
MyLinkedListV2{first=[d->a->b->c], size=4}
첫 번째 항목 삭제
MyLinkedListV2{first=[a->b->c], size=3}
중간 항목에 추가
MyLinkedListV2{first=[a->e->b->c], size=4}
중간 항목 삭제
MyLinkedListV2{first=[a->b->c], size=3}배열 리스트와 연결 리스트의 성능 비교
-
배열 리스트는 인덱스를 통해 추가나 삭제할 위치를 O(1)으로 빠르게 찾지만, 추가나 삭제 이후에 데이터를 한 칸씩 밀어야 하기 때문에 이 부분이 O(n)으로 오래 걸림
-
반면에 연결 리스트는 인덱스를 통해 추가나 삭제할 위치를 O(n)으로 느리게 찾지만, 찾은 이후에는 일부 노드의 참조값만 변경하면 되므로 이 부분이 O(1)으로 빠름
앞에 추가하는 경우
- 연결 리스트는 배열 리스트처럼 추가한 항목의 오른쪽에 있는 데이터를 모두 한 칸씩 밀지 않아도 됨
- 단순히 일부 노드의 참조만 변경
- 따라서 데이터를 앞쪽에 추가하는 경우 보통 연결 리스트가 더 좋은 성능을 제공함
- 배열 리스트: 데이터를 앞쪽에 추가하는 경우 모든 데이터를 오른쪽으로 한 칸씩 밀어야 한다. O(n)
- 연결 리스트: 데이터를 앞쪽에 추가하는 경우 일부 노드의 참조만 변경하면 된다. O(1)
마지막에 데이터를 추가하는 경우
- 배열 리스트
- 인덱스로 마지막 위치를 바로 찾을 수 있다. O(1)
데이터를 마지막에 추가하는 경우 데이터를 이동하지 않아도 된다. O(1)- 따라서 O(1)의 성능을 제공한다.
- 연결 리스트
- 노드를 마지막까지 순회해야 마지막 노드를 찾을 수 있다. 따라서 마지막 노드를 찾는데 O(n)의 시간이 걸린다.
- 데이터를 추가하는 경우 일부 노드의 참조만 변경하면 된다. O(1)
- 따라서 O(n)의 성능을 제공한다
배열 리스트 vs 연결 리스트 사용
- 데이터를 조회할 일이 많고, 뒷 부분에 데이터를 추가한다면 배열 리스트가 보통 더 좋은 성능을 제공함
- 앞쪽의 데이터를 추가하거나 삭제할 일이 많다면 연결 리스트를 사용하는 것이 보통 더 좋은 성능을 제공함
참고) 단일 연결 리스트, 이중 연결 리스트
- 위에서 구현한 연결 리스트는 한 방향으로만 이동하는 단일 연결 리스트
- 노드를 앞뒤로 모두 연결하는 이중 연결 리스트를 사용하면 성능을 더 개선할 수 있음
- 자바가 제공하는 연결 리스트는 이중 연결 리스트임
- 추가로 자바가 제공하는 연결 리스트는 마지막 노드를 참조하는 변수를 갖고 있어서, 뒤에 추가하거나 삭제하는 경우에도 O(1)의 성능을 제공함
이중 연결 리스트 예시
public class Node {
Object item;
Node next; //다음 노드 참조
Node prev; //이전 노드 참조
}마지막 노드를 참조하는 연결 리스트
public class LinkedList {
private Node first;
private Node last; //마지막 노드 참조
private int size = 0;
}연결 리스트 구현 3 - 제네릭 도입
- 연결 리스트에 제네릭을 도입하여 타입 안전성 높이기
- 여기서 사용되는 Node는 외부에서 사용되는 것이 아니라 연결 리스트 내부에서만 사용됨
- 따라서 중첩 클래스로 구현
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;
}
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> prev = getNode(index - 1);
newNode.next = prev.next;
prev.next = newNode;
}
size++;
}
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++;
}
return -1;
}
public int size() {
return size;
}
@Override
public String toString() {
return "MyLinkedListV3{" +
"first=" + first +
", size=" + size +
'}';
}
private static class Node<E> {
E item;
Node<E> next;
public Node(E item) {
this.item = item;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
Node<E> temp = this;
sb.append("[");
while (temp != null) {
sb.append(temp.item);
if (temp.next != null) {
sb.append("->");
}
temp = temp.next;
}
sb.append("]");
return sb.toString();
}
}
}-
MyLinkedListV3<E>로 제네릭 클래스를 선언함 -
Object로 처리하던 부분을 타입 매개변수<E>로 변경함 -
정적 중첩 클래스로 새로 선언한
Node<E>도 제네릭 타입으로 선언함Node클래스는MyLinkedList안에서만 사용되고, 외부에서는 사용할 이유가 없음- 이럴 때는 중첩 클래스를 사용하면 특정 클래스 안으로 클래스 선언을 숨길 수 있음
- 중첩 클래스를 사용하면
MyLinkedListV3입장에서 외부에 있는 Node 클래스보다 내부에 선언한 Node 클래스를 먼저 사용함
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
Backend development