LinkedList

Collections Framework의 LinkedList

링크드 리스트(Linked List)란?

링크드 리스트의 구성을 보면 서로 연속적이지만, 메모리에서의 연결은 연속적

이지 않다.

링크드 리스트의 첫 번째 구성요소는 참조값을 갖는 HEAD가 존재한다.

• HEAD를 통해 연결된 노드에 접근 할 수 있다.

LinkedList를 구성하는 노드(Node)는 두 부분으로 구성된다.

1. 노드의 값(데이터)

2. 다음 노드 주소를 저장하는 필드(참조하는 부분) -> 노드의 물리적인 위치는 일대일 참조이다.

Array와의 차이점

Array VS Linked List

1. Array와의 큰 차이점은 연결 리스트는 독립된 객체이다. LinkedList내에 존재하는 노드가 필요가 없어지면 삭제할 수 있지만 배열의 경우 구성된 셀은 별도의 객체가 아니므로 삭제할 수 없다. -> 셀의 값은 삭제가 가능하지만 셀 자체는 메모리에 적재되어 존재하게 된다 .

2. 두번쨰는 가변 크기이다.LinkedList는 목록 끝에 노드를 쉽게 추가할 수 있지만 이미 할당된 배열은 용량이 최대로 도달하면 배열 끝에 새로운 요소를 추가할 수 없다.

3. 세번째는 탐색 속도이다. 배열은 인덱스로 접근하면 O(1)로 빠르게 접근이 가능하다. LinkedList의 경우에는 HEAD부터 시작해서 다음 노드로 이동할 수 있다. 이는 요소에 엑세스하는 것에 대해서는 효율적이지 않다고 말할 수 있다. 그래서 최악의 경우 시간 복잡도는 O(N)이 걸린다.

특징

• 탐색은 ArrayList보다 느리다. -> ArrayList는 내부적으로 Array를 이용함.

  • 요소의 삽입/삭제는 ArrayList보다 빠르다.

• 순서를 보장하고 데이터 중복도 허용한다.

• 다음 노드를 가르키는 참조가 필요하기 떄문에 메모리를 더 많이 차지할 수 있다.

• 삽입/삭제 연산이 많이 발생하고, 요소 접근(읽기)가 상대적으로 적은 경우 적합하다.

LinkedList는 단방향 연결 리스트(Singly Linked List), 양방향 연결 리스트(Doubly Linked List), 양방향 원형 연결 리스트(Circular Doubly Linked List)가 있다.

---

구현

• class LinkedList<T>

// LinkedList 는 배열을 이용하지 않고, 객체와 객체를 연결해서 리스트를 생성 -> 하나의 element(Node) 가 하나의 객체이다.
public class LinkedList<T> {
    // ep : 내부적으로 다음과 같은 정보를 가지고 있어야 함.
    //  - head : 첫 번째 노드인가
    //  - tail : 누가 끝 노드인가
    //  - size : 몇개의 element 를 담을 수 있는 size
    private Node<T> head;
    private Node<T> tail;
    private int size = 0;

    // 하나의 element 는 inner class 로 정의한다.
    private static class Node<T> {
        // 하나의 노드는 data 와 다음 노드의 참조 주소를 갖는다. (필수 요소)
        private T data;
        private Node<T> next;

        public Node(T input) {
            this.data = input;
            this.next = null;
        }

        @Override
        public String toString() {
            return String.valueOf(this.data);
        }
    }
}

• addFirst(Element)

public void addFirst(T data) {
    Node<T> newNode = new Node<>(data);    // 노드라는 클래스는 인스턴스화, node 의 data = data, next = null
    newNode.next = head;                   // newNode.next는 head의 next를 가리키기 때문에 head.next = null
    head = newNode;
    this.size++;
    
    if (head.next == null) {               // 생성한 노드의 next 가 null 이면.. 즉, 생성된 노드 다음 노드가 없다면.
        tail = head;
    }
}

addFIrst()

• addLast(Element)

public void addLast(T data) {
    Node<T> newNode = new Node<>(data);
    if (size == 0) {
        addFirst(data);
    } else {
        tail.next = newNode;
        tail = newNode;
        this.size++;
    }
}

• Node node(index) : 내부적으로 Node를 반환해주는 메소드

private Node<T> node(int index) {
    Node<T> x = head;
    for (int i = 0; i < index; i++) {
        x = x.next;
    }

    return x;
}

• add(index, Element) : 특정 위치에 요소를 추가

public void add(int index, T data) {
    if (index == 0) {
        addFirst(data);
    } else {
        Node<T> tmp1 = node(index - 1);
        Node<T> tmp2 = tmp1.next;
        Node<T> newNode = new Node<>(data);
        tmp1.next = newNode;
        newNode.next = tmp2;
        this.size++;

        if (newNode.next == null) {
            tail = newNode;
        }
    }
}

• toString() 오버라이딩

@Override
public String toString() {
    if (head == null) {
        return "[]";
    }
    Node tmp = head;
    String str = "[";
    while (tmp.next != null) {
        str += tmp.data + ", ";
        tmp = tmp.next;
    }
    str += tmp.data;

    return str + "]";
}

• removeFirst

public Object removeFirst() {
    Node tmp = head;
    head = head.next;
    Object removedData = tmp.data;
    tmp = null;
    size--;
    return removedData;
}

• remove(int index)

public Object remove(int index) {
    if (index == 0) {
        return removeFirst();
    }
    // index 이전 Node
    Node tmp = node(index - 1);
    // index에 해당하는 Node
    Node deletedNode = tmp.next;
    tmp.next = tmp.next.next;
    Object removedData = deletedNode.data;

    // 삭제하는 Node가 tail일 경우
    if (deletedNode == tail) {
        tail = tmp;
    }
    deletedNode = null;
    size--;
    return removedData;
}

• removeLast()

// 삭제 작업의 시간 복잡도 : 최악의 경우
public Object removeLast() {
    return remove(size - 1);
}

• size()

public int size() {
    return size;
}

• get(int index)

public Object get(int index) {
    return node(index).data;
}

• indexOf(Object node)

public int indexOf(Object node) {
    Node tmp = head;
    int index = 0;

    while (tmp.data != node) {
        tmp = tmp.next;
        index++;
        if (tmp == null) return -1;
    }
    return index;
}

• inner class ListIterator

public ListIterator listIterator() {
    return new ListIterator();
}

class ListIterator {
    private Node next;
    private Node lastReturned;
    private int nextIndex;

    ListIterator() {
        next = head;
        nextIndex = 0;
    }
}

• Iterator next(), hasNext()

public Object next() {
    lastReturned = next;
    next = next.next;
    nextIndex++;
    return lastReturned.data;
}

public boolean hasNext() {
    return nextIndex < size();
}

참고 : https://opentutorials.org/module/1335/8857