[Java] 김영한의 자바 중급 2편 #4 - LinkedList

1. 노드와 연결1

1.1. 배열 리스트의 단점

• 배열의 사용하지 않는 공간 낭비
• 배열의 중간에 데이터를 추가할 때
  • 데이터를 추가할 때 기존 데이터들을 오른쪽으로 이동시켜야 한다.
  • 데이터를 삭제할 때 빈 공간을 채우기 위해 데이터들을 왼쪽으로 이동시켜야 한다.

1.2. 노드와 연결

낭비되는 메모리 없이 필요한 만큼 메모리를 확보해서 사용하고, 또 앞이나 중간에 데이터를 추가하거나 삭제할 때도 효율적인 자료 구조가 있는데, 바로 노드를 만들고 서로 연결하는 방식이다.

Node Class

public class Node{
	// 저장할 데이터
	Object item;
	// 연결할 노드의 참조
	Node next;
}

1.3. 간단한 예제

Node Class

package collection.link;

public class Node {

    Object item;
    Node next;

    public Node(Object item) {
        this.item = item;
    }
}

item은 저장할 데이터를 가지고 있으며, next는 다음 Node Class의 참조 위치를 가리키고 있다.

따라서 Node를 생성할 때 생성자인 item만 넣어주고 그 다음에 next에 새로 생성한 Node 클래스의 참조값을 넣어주면 된다.

Main Class

package collection.link;

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;
        }
    }
}

// result
모든 노드 탐색하기
A
B
C

1.4. toString 직접 구현

[A→B→C] 와 같이 한 눈에 Node의 구조를 확인할 수 있도록 toString을 직접 구현해보자.

Node Class

package collection.link;

public class Node {

    Object item;
    Node next;

    public Node(Object item) {
        this.item = item;
    }

    @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();
    }
}

• 반복문 안에서 문자를 계속 더하기 때문에 StringBuilder를 사용하였다.
  • String으로 계속 더한다면 내부적으로 계속 문자를 생성하고 GC하는 과정이 반복되기 때문에 이럴때는 StringBuilder를 사용하는 것이 더욱 좋다고 한다.
• while loop을 돌면서 x.next(Node의 다음 참조값)이 null일 때까지 탐색하여 item 값을 출력해준다.

Main Class

package collection.link;

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);
    }
}

// result
연결된 노드 출력하기
[A->B->C]

2. 노드와 연결3

이제 다른 다양한 기능들을 만들어보자.

• 모든 노드 탐색하기
• 마지막 노드 조회하기
• 특정 index의 노드 조회하기
• 노드에 데이터 추가하기

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);

        // 1. 모든 노드 탐색하기
        System.out.println("1. 모든 노드 탐색하기");
        printAll(first);

        // 2. 마지막 노드 조회하기
        System.out.println("2. 마지막 노드 조회하기");
        Node lastNode = getLastNode(first);
        System.out.println("lastNode = " + lastNode);

        // 3. 특정 index의 노드 조회하기
        System.out.println("3. 특정 index의 노드 조회하기");
        int index = 2;
        Node index2Node = getNode(first, index);
        System.out.println("index2Node = " + index2Node.item);

        // 4. 데이터 추가하기
        System.out.println("4. 데이터 추가하기");
        add(first, "D");
        System.out.println(first);

        add(first, "E");
        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);
    }
}

// result
[A->B->C]
1. 모든 노드 탐색하기
A
B
C
2. 마지막 노드 조회하기
lastNode = [C]
3. 특정 index의 노드 조회하기
index2Node = C
4. 데이터 추가하기
[A->B->C->D]
[A->B->C->D->E]

2.1. 간략한 정리

• 노드 : 데이터와 다음 노드에 대한 참조를 가지고 있는 클래스
• 데이터를 추가할 때 동적으로 필요한 만큼의 노드만 만들어서 연결하면 된다. 따라서 배열처럼 미리 공간을 확보하는 등 메모리를 낭비하지 않는다.
  • 물론 next 필드를 통해 참조값을 보관해야 하기 때문에 배열과 비교하여 추가적인 메모리 낭비도 발생한다.
• 이렇게 각각의 노드를 연결(링크)해서 사용하는 자료 구조를 리스트로 만들 수 있는데 이를 연결 리스트라고 한다.

3. 직접 구현하는 연결 리스트1 - 시작

MyLinkedList를 직접 구현해본다.

MyLinkedList V1

package collection.link;

public class MyLinkedListV1 {

    private Node first;
    private int size = 0;

    public void add(Object o) {
        Node newNode = new Node(o);

        if (first == null) {
            first = newNode;
        } else {
            Node lastNode = getLastNode();
            lastNode.next = newNode;
        }

        size++;
    }

    private Node getLastNode() {
        Node x = first;

        // next field가 null인 Node를 찾아서 반환해야 한다.
        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 x = getNode(index);
        return x.item;
    }

    public Node getNode(int index) {
        Node x = first;

        // index번째 Node를 찾아서 반환해야 한다.
        for (int i = 0; i < index; i++) {
            x = x.next;
        }

        return x;
    }

    public int indexOf(Object o) {
        int index = 0;

        // first Node부터 순차적으로 탐색하면서 o와 같은 객체를 찾아서 그 index를 반환해야 한다.
        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 +
                '}';
    }

}

Main Class

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);
    }
}

 

 

 

 

• Object get(int index) : 특정 위치에 있는 데이터를 반환한다. O(n)
• void add(Object e) : 마지막에 데이터를 추가한다. O(n)
• Object set(int index, Object element) : 특정 위치에 있는 데이터를 찾아서 변경 후 기존 값을 반환한다. O(n)
• int indexOf(Object o) : 모든 노드를 순회하면서 equals() 메서드로 데이터를 검색하고 같다면 검색된 위치를 반환한다.

4. 직접 구현하는 연결 리스트2 - 추가와 삭제

다음의 2가지 기능을 만들어보자.

• void add(int index, Object e) : 특정 위치에 데이터를 추가한다.
• Object remove(int index) : 특정 위치에 있는 데이터를 제거한다.

4.1. 구현 방법 정리

4.1.1. 첫 번째 위치에 데이터를 추가

[A → B → C]의 연결 리스트가 있다고 가정해보자.

• new Node(data)로 해서 newNode를 만든다.
• newNode.next에는 first를 집어넣는다.
• 기존 first에 newNode를 넣어서 연결해준다.

4.1.2. 첫 번째 위치의 데이터 삭제

[D → A → B → C]의 연결 리스트가 있다고 가정해보자.

위 연결 리스트를 [A → B → C]로 변경해야 한다.

• 삭제 대상을 선택한다.
• first에 삭제 대상의 다음 노드를 연결한다.
• 삭제 대상의 데이터를 초기화한다.

4.1.3. 중간 위치에 데이터를 추가하는 케이스

[A → B → C]로 만들어진 노드의 1번 인덱스 위치에 E를 추가하여, [A → E → B → C]로 변경한다고 가정

• newNode를 생성한다.
• 노드가 입력될 위치의 직전 노드(prevNode)를 찾는다.
• newNode와 prev.next를 연결한다.
• prev.next에는 newNode의 참조값으로 넣어준다.

4.1.4. 중간 위치에 데이터를 삭제하는 케이스

• 삭제 대상을 찾는다
• 삭제 대상의 직전 노드(prevNode)도 찾는다.
• prevNode의 다음 노드를 삭제 노드의 다음 노드와 연결한다 (prev.next = removeNode.next)
• 삭제 노드의 데이터를 초기화한다.

4.2. 직접 코드로 구현하기

MyLinkedListV2 Class

package collection.link;

public class MyLinkedListV2 {

    private Node first;
    private int size = 0;

    public void add(Object o) {
        Node newNode = new Node(o);

        if (first == null) {
            first = newNode;
        } else {
            Node lastNode = getLastNode();
            lastNode.next = newNode;
        }

        size++;
    }

    private Node getLastNode() {
        Node x = first;

        // next field가 null인 Node를 찾아서 반환해야 한다.
        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;   // return 해야 함

        if (index == 0) {
            first = removeNode.next;
        } else {
            Node prev = getNode(index - 1);
            prev.next = removeNode.next;
        }
        // removeNode의 item, next field를 null로 만들어준다.
        removeNode.item = null;
        removeNode.next = null;
        size--;

        return removedItem;
    }

    public Object get(int index) {
        Node x = getNode(index);
        return x.item;
    }

    public Node getNode(int index) {
        Node x = first;

        // index번째 Node를 찾아서 반환해야 한다.
        for (int i = 0; i < index; i++) {
            x = x.next;
        }

        return x;
    }

    public int indexOf(Object o) {
        int index = 0;

        // first Node부터 순차적으로 탐색하면서 o와 같은 객체를 찾아서 그 index를 반환해야 한다.
        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 +
                '}';
    }

}

Main Class

package collection.link;

public class MyLinkedListV2Main {

    public static void main(String[] args) {

        MyLinkedListV2 list = new MyLinkedListV2();

        list.add("a");
        list.add("b");
        list.add("c");
        System.out.println(list);

        System.out.println("첫 번째 항목에 추가 : O(1)");
        list.add(0, "d");
        System.out.println(list);

        System.out.println("첫 번째 항목 삭제 : O(1)");
        list.remove(0);
        System.out.println(list);

        System.out.println("중간 항목에 추가 : O(n)");
        list.add(1, "e");
        System.out.println(list);

        System.out.println("중간 항목 삭제 : O(n)");
        list.remove(1);
        System.out.println(list);
    }
}

// result
MyLinkedListV1{first=[a->b->c], size=3}
첫 번째 항목에 추가 : O(1)
MyLinkedListV1{first=[d->a->b->c], size=4}
첫 번째 항목 삭제 : O(1)
MyLinkedListV1{first=[a->b->c], size=3}
중간 항목에 추가 : O(n)
MyLinkedListV1{first=[a->e->b->c], size=4}
중간 항목 삭제 : O(n)
MyLinkedListV1{first=[a->b->c], size=3}

4.3. (직접 만든) 배열 리스트와 연결 리스트 성능 비교 표

• 인덱스 조회
  • 배열 리스트 : O(1)
  • 연결 리스트 : O(n)
• 검색
  • 배열 리스트 : O(n)
  • 연결 리스트 : O(n)
• 앞에 추가(삭제)
  • 배열 리스트 : O(n)
  • 연결 리스트 : O(1)
• 뒤에 추가(삭제)
  • 배열 리스트 : O(1)
  • 연결 리스트 : O(n)
• 평균 추가(삭제)
  • 배열 리스트 : O(n)
  • 연결 리스트 : O(1)

배열 리스트 vs 연결 리스트 사용

데이터를 조회할 일이 많고, 뒷 부분에 데이터를 추가한다면 배열 리스트가 보통 더 좋은 성능을 제공한다.

앞쪽의 데이터를 추가하거나 삭제할 일이 많다면 연결 리스트를 사용하는 것이 보통 더 좋은 성능을 제공한다.

(참고) 단일 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;
}

5. 직접 구현하는 연결 리스트3 - 제네릭 도입

MyLinkedListV3 Class

package collection.link;

public class MyLinkedListV3<E> {

    private Node<E> first;
    private int size = 0;

    public void add(E o) {
        Node<E> newNode = new Node<>(o);

        if (first == null) {
            first = newNode;
        } else {
            Node<E> lastNode = getLastNode();
            lastNode.next = newNode;
        }

        size++;
    }

    private Node<E> getLastNode() {
        Node<E> x = first;

        // next field가 null인 Node를 찾아서 반환해야 한다.
        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;   // return 해야 함

        if (index == 0) {
            first = removeNode.next;
        } else {
            Node<E> prev = getNode(index - 1);
            prev.next = removeNode.next;
        }
        // removeNode의 item, next field를 null로 만들어준다.
        removeNode.item = null;
        removeNode.next = null;
        size--;

        return removedItem;
    }

    public E get(int index) {
        Node<E> x = getNode(index);
        return x.item;
    }

    public Node<E> getNode(int index) {
        Node<E> x = first;

        // index번째 Node를 찾아서 반환해야 한다.
        for (int i = 0; i < index; i++) {
            x = x.next;
        }

        return x;
    }

    public int indexOf(E o) {
        int index = 0;

        // first Node부터 순차적으로 탐색하면서 o와 같은 객체를 찾아서 그 index를 반환해야 한다.
        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 "MyLinkedListV1{" +
                "first=" + first +
                ", size=" + size +
                '}';
    }

    private static class Node<E> {
        E item;
        Node<E> next;

        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();
        }
    }

}

Main Class

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);
    }
}