'김영한의 실전 자바 - 중급 2편' 강의를 들으면서 복습할만한 내용을 정리하였다.

4. 컬렉션 프레임워크 - LinkedList

4.1 배열 리스트(ArrayList)의 단점

배열 리스트는 내부에 배열을 사용해서 데이터를 보관하고 관리한다.

배열의 사용하지 않는 공간 낭비

배열은 필요한 배열의 크기를 미리 확보해야 한다. 데이터가 얼마나 추가될지 예측할 수 없는 경우 나머지 공간은 사용되지 않고 낭비된다.

배열의 중간에 데이터 추가

배열의 앞이나 중간에 데이터를 추가하면 추가할 데이터의 공간을 확보하기 위해 기존 데이터들을 오른쪽으로 이동해야 한다. 그리고 삭제의 경우에는 빈 공간을 채우기 위해 왼쪽으로 이동해야 한다.

이렇게 앞이나 중간에 데이터를 추가하거나 삭제하는 경우 많은 데이터를 이동해야 하기 때문에 성능이 좋지 않다.

4.2 노드와 연결

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

노드

public class Node {
	Object item;
    Node next;
}

노드 클래스는 내부에 저장할 데이터인 item 과, 다음으로 연결할 노드의 참조인 next 를 가진다.

노드의 구조

4.3 직접 구현하는 연결 리스트

노드와 연결 구조를 통해서 리스트로 만든 자료 구조를 연결 리스트(LinkedList)라 한다.

리스트 자료구조

순서가 있고, 중복을 허용하는 자료 구조를 리스트(List)라 한다.

앞서 직접 구현한 ArrayList 도 같은 리스트이다. 리스트를 사용하는 입장에서는 ArrayList 와 LinkedList 의 내부가 어떻게 돌아가는지는 몰라도, 순서가 있고, 중복을 허용하는 자료 구조구나 생각하고 사용할 수 있어야 한다.

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 remove(int index) {
        Node<E> node = getNode(index);
        E removedItem = node.item;
        if (index == 0) {
            first = node.next;
        } else {
            Node<E> prev = getNode(index - 1);
            prev.next = node.next;
        }
        node.next = null;
        node.item = null;
        size--;
        return removedItem;
    }

    public E set(int index, E element) {
        Node<E> x = getNode(index);
        E oldValue = x.item;
        x.item = element;
        return oldValue;
    }

    public E get(int index) {
        return getNode(index).item;
    }

    public int indexOf(E e) {
        int index = 0;
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item.equals(e)) return index;
            index++;
        }
        return -1;
    }

    public int size() {
        return size;
    }

    @Override
    public String toString() {
        return "MyLinkedListV1{" +
                "first=" + first +
                ", size=" + size +
                '}';
    }

    private Node<E> getNode(int index) {
        Node<E> x = first;
        for (int i = 0; i < index; i++) {
            x = x.next;
        }
        return x;
    }

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

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

• 만약 첫 노드 추가라면 first 에 연결한다.
• 마지막 노드를 찾아 새로운 노드를 가리키도록 해서 새로운 노드를 추가한다.
• x.next != null : 노드가 가리키는 다음 노드가 없다면 이 노드는 마지막 노드이다.

특정 index에 데이터 추가

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

• index == 0 : 첫번째에 노드를 추가한다. 노드의 다음을 기존 첫번째 노드를 가리키도록 대입하고, 기존의 첫번째 노드는 새롭게 추가되는 노드로 수정한다.
• getNode(index - 1) : 추가하려는 index 앞의 노드를 찾아서 새롭게 추가하는 노드를 가리키도록 하고, 추가되는 노드는 prev 노드가 가리키던 노드를 가리키도록 수정한다.

특정한 index의 노드 삭제

public E remove(int index) {
	Node<E> node = getNode(index);
    E removedItem = node.item;
    if (index == 0) {
    	first = node.next;
	} else {
    	Node<E> prev = getNode(index - 1);
        prev.next = node.next;
	}
    node.next = null;
    node.item = null;
    size--;
    return removedItem;
}

private Node<E> getNode(int index) {
	Node<E> x = first;
    for (int i = 0; i < index; i++) {
    	x = x.next;
	}
    return x;
}

• index == 0 : 만약 첫번째 노드를 삭제한다면 삭제하는 노드의 다음 노드를 first 가 가리키도록 한다.
• prev.next = node.next : 삭제하는 노드의 prev 노드가 삭제하는 노드가 가리키는 노드를 가리키도록 수정하여 삭제하는 노드를 가리키는 참조가 더 이상 없게 만들어 GC의 대상이 되도록 한다.

제네릭 도입

제네릭을 도입해서 타입 안정성을 높이고 Node 는 외부에서 사용되는 것이 아니라 연결 리스트 내부에서만 사용되기 때문에 중첩 클래스로 만든다.

정적 중첩 클래스 Node

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

4.4 구현한 배열 리스트와 연결 리스트 비교

기능	배열 리스트	연결 리스트
인덱스 조회	O(1)	O(n)
검색	O(n)	O(n)
앞에 추가(삭제)	O(n)	O(1)
중간 추가(삭제)	O(n)	O(n)
뒤에 추가(삭제)	O(1)	O(n)

• 배열 리스트는 인덱스를 통해 위치를 찾는데 O(1)로 빠르게 찾는다.
• 연결 리스트는 인덱스를 통해 위치를 찾는데 O(n)으로 느리게 찾는다.
• 배열 리스트는 요소를 앞/중간에 추가/삭제 할 때 데이터를 이동해야 하므로 O(n) 이 걸린다.
• 연결 리스트는 요소를 중간/뒤에 추가/삭제 할 때 데이터의 참조만 바꾸면 되므로 O(1) 이 걸리지만 위치를 찾느라고 O(n) 이 걸린다.
• 배열 리스트는 요소를 뒤에 추가할 때 데이터를 이동하지 않고 인덱스로 바로 찾을 수 있으므로 O(1) 이 걸린다.
• 연결 리스트는 요소를 앞에 추가할 때 데이터의 참조만 변경하면 되므로 O(1) 이걸린다.

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

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

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

참고 - 단일 연결 리스트, 이중 연결 리스트

구현한 연결 리스트는 한 방향으로만 이동하는 단일 연결 리스트이다. 노드를 앞뒤로 모두 연결하는 이중 연결 리스트를 사용하면 성능을 더 개선할 수 있다. (뒤에 데이터 추가도 O(1) 이 걸린다.)

자바가 제공하는 연결 리스트는 이중 연결 리스트다.