[Java] LinkedList

1. ArrayList 의 단점

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

• 데이터 추가시 기존 데이터들 오른쪽 이동

• 데이터 삭제시 기존 데이터들 왼쪽 이동

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

---

2. 노드와 연결

낭비되는 메모리 없이 필요한 만큼만 메모리를 확보해서 사용한다.
노드를 만들고 각 노드를 서로 연결하는 방식이다.

Node

public class Node {
	Object item;
    Node next;
}

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

---

3. 직접 구현하는 LinkedList

노드와의 연결 구조를 통해 리스트로 만든 자료 구조가 LinkedList 이다.

public class MyLinkedList<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에 연결한다.
• 마지막 노드를 찾아 새로운 노드를 가르키도록 새로운 노드를 추가한다.

• while (x.next != null)

  다음 노드가 없으면 이 노드는 마지막 노드이다.

특정 위치에 데이터 추가

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

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

• index == 0 이면
  newNode.next = first; 다음 노드에 현재 첫 노드를 옮기고
  first = newNode; newNode를 첫 노드로 수정한다.

• getNode(index - 1); : 추가하려는 index 앞의 노드를 찾아서 새롭게 추가하는 노드를 가리키도록 하고, 추가되는 노드는 prev 노드가 가리키던 노드를 가리키도록 수정한다.

특정 위치의 데이터 삭제

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 = node.next 삭제하는 노드의 다음 노드를 first가 가리키도록 한다.

• prev.next = node.next; : 삭제하는 prev 노드가 삭제하는 노드가 가리키는 노드를 가리키도록 수정한다.