0. 개요
LinkedList에 대해 알아보자.
1. 노드와 연결1
배열 리스트의 단점
배열 리스트는 내부에 배열을 사용해서 데이터를 보관하고 관리한다. 이로 인해 다음과 같은 단점을 가진다.
- 1. 배열의 사용하지 않는 공간 낭비
- 배열은 필요한 배열의 크기를 미리 확보해야 한다.
- 2. 배열의 중간에 데이터 추가
- 배열의 앞이나 중간에 데이터를 추가하면 추가할 데이터의 공간을 확보하기 위해 기존 데이터들을 오른쪽으로 이동해야 한다. 그리고 삭제의 경우에는 빈 공간을 채우기 위해 왼쪽으로 이동해야 한다.
- 이렇게 앞이나 중간에 데이터를 추가하거나 삭제하는 경우 많은 데이터를 이동해야 하기 때문에 성능이 좋지 않다.
1) 노드와 연결
- 낭비되는 메모리 없이 딱 필요한 만큼만 메모리를 확보해서 사용하고, 또 앞이나 중간에 데이터를 추가하거나 삭제할 때도 효율적인 자료구조가 있는데, 바로 노드를 만들고 각 노드를 서로 연결하는 방식이다.
노드 클래스
public class Node { Object item; Node next; public }
- 노드 클래스는 내부에 저장할 데이터인
item과 다음으로 연결한 노드의 참조인next를 가진다.- 이 노드 클래스를 사용해서 데이터 A,B,C 를 순서대로 연결해보자.
노드에 데이터 A 추가
Node인스턴스를 생성하고item에 "A"를 넣어준다.
노드에 데이터 B 추가
Node인스턴스를 생성하고item에 "B"를 넣어준다.- 처음 만든 노드의
Node next필드에 새로 만든 노드의 참조값을 넣어준다.- 이렇게 하면 첫 번째 노드와 두 번째 노드가 서로 연결된다.
- 첫번째 노드의
node.next를 호출하면 두 번째 노드를 구할 수 있다.
노드에 데이터 C 추가
Node인스턴스를 생성하고item에 "C"를 넣어준다.- 두 번째 만든 노드의
Node next필드에 새로 만든 노드의 참조값을 넣어준다.- 이렇게하면 두 번째 노드와 세 번째 노드가 서로 연결된다.
- 첫 번째 노드의
node.next를 호출하면 두 번째 노드를 구할 수 있다.- 두 번째 노드의
node.next를 호출하면 세 번째 노드를 구할 수 있다.- 첫 번째 노드의
node.next.next를 호출하면 세 번째 노드를 구할 수 있다.
지금까지 설명한 내용을 코드로 직접 만들어보자.
public class Node { Object item; Node next; public Node(Object item){ this.item = item; } }
- 필드의 접근 제어자는
private으로 선언하는 것이 좋지만, 이 예제에서는 설명을 단순하게 하기 위해 디폴트 접근 제어자를 사용했다.public class NodeMain1 { 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("모든 노트 탐색하기"); Node x = first; while (x != null) { System.out.println(x.item); x = x.next; } } }
모든 노드 탐색하기(코드 분석)
모든 노드를 탐색하는 방법을 알아보자.
Nodex x = first; while (x != null){ System.out.println(x.itme); x = x.next; }실행 결과
A B C
순서대로 분석해보자.
Node x는 처음 노드부터 순서대로 이동하면서 모든 노드를 가리킨다. 처음에Node x는x01을 참조한다.- 그리고 while 문을 통해 반복해서 다음 노드를 가리킨다.
while문은 다음 노드가 없을 때 까지 반복한다.Node.next의 참조값이null이면 노드의 끝이다.
반복 실행 순서
Node x = x01
x.item출력 "A"
x = x.next(x02)
Node x = x02
x.item출력 "B"
x = x.next(x03)
Node x = x03
x.item출력 C
x = x.next(null)
Node x = null
while(x != null)조건에서x=null이므로 종료
정리
Node인스턴스를 생성하고item에 "해당 노드의 알파벳"을 넣어준다.
- 해당 노드의 "알파벳 변수" 에 생성된 노드의 참조를 보관한다.
- 이걸 계속 반복
2. 노드와 연결2
1) toString() - IDE
노드의 연결 상태를 더 편하게 보기 위해 toString()을 오버라이딩 해보자.
toString() 을 사용함으로써 객체의 정보를 확인
public class Node { Object item; Node next; public Node(Object item){ this.item = item; } //IDE 생성 toString() @Override public String toString() { return "Node{" + "item=" + item + ", next=" + next + '}'; } }public class NodeMain2 { 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("연결된 노드 출력하기"); System.out.println(first); } }실행 결과
연결된 노드 출력하기 Node{item=A, next=Node{item=B, next=Node{item=C, next=null}}}
- IDE의 도움을 받아서 만든
toString()으로 필요한 정보를 확인할 수는 있지만, 한눈에 보기에는 좀 복잡하다.- 대신에
[A->B->C]와 같이 필요한 정보만 편리하게 확인할 수 있게toString()을 직접 구현해보자
2) toString() - 직접 구현
StringBuilder를 사용함으로써append와 같은 기능을 편리하게 사용 가능[A->B->C]와 같이 데이터와 연결 구조를 한눈에 볼 수 있도록toString()을 직접 구현해보자.
public class Node { Object item; Node next; @Override public String toString() { 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(); } }
- 직접 만든
toString()은 연결된 모든 노드를 탐색해서 출력하고[A->B->C]와 같이 출력한다.- 반복문 안에서 문자를 더하기 때문에
StringBuilder를 사용하는 것이 효과적이다.- 구현은 앞서 살펴본 모든 노드 탐색하기와 같다.
while을 사용해서 다음 노드가 없을 때 까지 반복한다.
x = x.next: 탐색의 위치를 다음으로 이동한다. 현재 탐색중인 노드가x이다.x.next를 통해x의 참조값을 다음 노드로 변경한다.
3. 노드와 연결3
노드와 연결을 활용해서 다양한 기능을 만들어보자.
- 모든 노드 탐색하기
- 마지막 노드 조회하기
- 특정 index의 노드 조회하기
- 노드에 데이터 추가하기
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 = " + 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 void printAll(Node node) { Node x = node; while (x != null) { System.out.println(x.item); x = x.next; } } private static Node getLastNode(Node node) { Node x = node; while (x.next != null) { x = x.next; } return x; } 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, String param) { Node lastNode = getLastNode(node); lastNode.next = new Node(param); } }
정리
- 노드는 내부에 데이터와 다음 노드에 대한 참조를 가지고 있다.
- 지금까지 설명한 구조는 각각의 노드가 참조를 통해 연결(Link, 링크) 되어 있다.
- 데이터를 추가할 때 동적으로 필요한 만큼의 노드만 만들어서 연결하면 된다. 따라서 배열과 다르게 메모리를 낭비하지 않는다.
- 물론
next필드를 통해 참조값을 보관해야 하기 때문에 배열과 비교해서 추가적인 메모리 낭비도 발생한다.
- 물론
- 노드와 연결 구조를 처음 공부하면 이해하기 쉽지않다. 하지만 반복해서 학습하고 또 코드도 직접 만들어보면서 반드시 이해해야 한다. 이해가 어렵다면 코드를 따라서 종이에 천천히 노드를 그려보면 이해가 될 것이다.
- 이렇게 각각의 노드를 연결(링크)해서 사용하는 자료 구조로 리스트를 만들 수 있는데, 이것을 연결 리스트라 한다.
4. 직접 구현하는 연결 리스트1 - 시작
우리는 앞서 배열을 통해서 리스트를 만들었는데 이것을 배열 리스트(ArrayList)라 한다. 이번에는 배열이 아닌 앞서 학습한 노드와 연결 구조를 통해서 리스트를 만들어보자. 이런 자료 구조를 연결 리스트(LinkedList)라 한다.
연결 리스트는 배열 리스트의 단점인 메모리 낭비, 중간 위치의 데이터 추가에 대한 성능 문제를 어느 정도 극복할 수 있다.
리스트 자료구조
순서가 있고, 중복을 허용하는 자료 구조를 리스트라 한다.
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)
- 마지막에 데이터를 추가한다.
- 새로운 노드를 만들고, 마지막 노드를 찾아서 새로운 노드를 마지막에 연결한다.
- 만약 노드가 하나도 없다면 새로운 노드를 만들고
first연결한다.
- Object set(int index, Object element)
- 특정 위치에 있는 데이터를 찾아서 변경한다. 그리고 기존 값을 반환한다.
getNode(index)를 통해 특정 위치에 있는 노드를 찾고, 단순히 그 노드에 있는item데이터를 변경한다.
- Object get(int index)
- 특정 위치에 있는 데이터를 반환한다.
getNode(index)를 통해 특정 위치에 있는 노드를 찾고, 해당 노드에 있는 값을 반환한다.
- int indexOf(Object o)
- 데이터를 검색하고, 검색된 위치를 반환한다.
- 모든 노드를 순회하면서
equals()를 사용해서 같은 데이터가 있는지 찾는다.
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에 있는 코드를 거의 그대로 사용했다.
직접 구현하는 연결 리스트2 - 추가와 삭제
특정 위치에 데이터를 추가하고, 삭제하는 기능을 만들어보자.
다음 두 기능을 추가하면 된다.
void add(int index, Object e)
- 특정 위치에 데이터를 추가한다.
- 내부에서 노드도 함께 추가된다.
Object remove(int index)
- 특정 위치에 있는 데이터를 제거한다.
- 내부에서 노드도 함께 제거된다.
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; } 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 prev = getNode(index - 1); newNode.next = prev.next; prev.next = newNode; } size++; } 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 { Node prev = getNode(index - 1); prev.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++; } return -1; } public int size() { return size; } @Override public String toString() { return "MyLinkedListV2{" + "first=" + first + ", size=" + size + '}'; } }
public class MyLinkedList2Main { 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); } }
직접 만든 배열 리스트와 연결 리스트의 성능 비교 표
배열 리스트 vs 연결 리스트 사용
- 데이터를 조회할 일이 많고, 뒷 부분에 데이터를 추가한다면 배열 리스트가 보통 더 좋은 성능을 제공한다.
- 앞쪽의 데이터를 추가하거나 삭제할 일이 많다면 연결 리스트를 사용하는 것이 보통 더 좋은 성능을 제공한다.
참고 - 단일 연결 리스트, 이중 연결 리스트
- 우리가 구현한 연결 리스트는 한 방향으로만 이동하는 단일 연결 리스트다.
- 노드를 앞뒤로 모두 연결하는 이중 연결 리스트를 사용하면 성능을 더 개선할 수 있다.
- 추가로 자바가 제공하는 연결리스트는 마지막 노드를 참조하는 변수를 가지고 있어서, 뒤에 추가하거나 삭제하는 경우에도
O(1)의 성능을 제공한다.
직접 구현하는 연결 리스트4 - 제네릭 도입
MyLinkedListV3를MyLinkedListV3<E>로 제네릭 클래스를 선언했다.Object로 처리하던 부분을 타입 매개변수<E>로 변경했다.- 정적 중첩 클래스로 새로 선언한
Node<E>도 제네릭 타입으로 선언했다.
중첩 클래스 예시)
class OuterClass { ... static class StaticNestedClass { ... } }
- 이렇게 클래스 안에서 클래스를 선언하는 것을 중첩 클래스라 한다.
- 중첩 클래스는 특정 클래스 안에서만 사용될 때 주로 사용한다.
Node클래스는MyLinkedList안에서만 사용된다. 외부에서는 사용할 이유가 없다.- 이럴 때 중첩 클래스를 사용하면 특정 클래스 안으로 클래스 선언을 숨길 수 있다.
- 중첩 클래스를 사용하면
MyLinkedListV3입장에서 외부에 있는Node클래스보다 내부에 선언한Node클래스를 먼저 사용한다.
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); } }제네릭 덕분에 타입 안정성 있는 자료 구조를 만들 수 있다.
안녕하세요. wony입니다.