링크드리스트(Linked List)

https://en.wikipedia.org/wiki/Linked_list

• 배열은 원소를 삽입, 삭제할때 새로운 저장 공간을 새로 만들거나 원소를 당겨버리는 행동을 하는 등 시간복잡도가 O(n)이 걸리곤 했다. 링크드 리스트는 이 삽입, 삭제에 걸리는 시간을 줄이기 위해 탄생한 자료구조
• 자료를 저장할때 자료값만 저장하는 것이 아니라 다음 자료가 저장되어있는 위치를 함께 저장시키는 자료구조
• 저장공간의 크기는 가변적이다.
• 메모리 공간이 배열과는 달리 연속적으로 구성되어 있지 않다. 원소의 저장이 메모리에 연속으로 들어가는 것이 아니라 원소값과 다음 원소값이 저장되어있는 주소값이 함께 저장되어 있어 그 주소값을 찾아 원소를 탐색해 나간다. 그러므로 배열(Array)의 인덱스(Index)를 통한 접근이 불가능하다.

장점

• 새로운 원소를 삽입할때 시간복잡도 O(1)

https://en.wikipedia.org/wiki/Linked_list

• 원소를 삭제할때 시간복잡도 O(1)

https://en.wikipedia.org/wiki/Linked_list

• 새로운 원소가 삽입되거나 삭제될때 배열과는 달리 새로운 저장공간을 만들어줄 필요가 없음. 메모리가 조금 더 효율적

단점

• 원소 조회시 배열처럼 인덱스를 통해 바로 접근하는 것이 아니라 연결된 다음 주소를 타고타고 들어가며 조회해야하므로 O(n)
• 원소 수정 역시 조회를 먼저 한뒤 값을 변경하게 되므로 조회에 필요한 O(n)이 시간복잡도가 걸리게 된다.

 

Code

단방향 링크드리스트

import java.util.NoSuchElementException;

class Main {
    public static void main(String[] args) {
      MyLinkedList<Integer> linkedList = new MyLinkedList<>();
      linkedList.add(1);
      linkedList.add(2);
      linkedList.add(3);
      linkedList.add(0, 0);
      linkedList.add(2, 7);
      printElements(linkedList.size(), linkedList);

      linkedList.delete(0);
      linkedList.delete(0);
      linkedList.delete(0);
      linkedList.delete(0);
      printElements(linkedList.size(), linkedList);
    }

    public static void printElements(int size, MyLinkedList<Integer> linkedList) {
      for (int i = 0; i < linkedList.size(); i++) {
        System.out.print(linkedList.get(i) + " ");
      }
      System.out.println();
    }
}

class Node<E> {
  E data;
  Node<E> next;

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

class MyLinkedList<E> {
  private Node<E> head;
  private Node<E> tail;
  private int size;

  public MyLinkedList() {
    this.head = null;
    this.tail = null;
    this.size = 0;
  }

  // 특정 위치 노드 반환
  private Node<E> searchNode(int index) {
    validateIndex(index, size);
    Node<E> node = head;
    for (int i = 0; i < index; i++) {
      node = node.next;
    }
    return node;
  }

  // 링크드리스트 값 추가
  public void add(E value) {
    if (size == 0) {
      addFirst(value);
      return;
    }
    Node<E> node = new Node<E>(value);
    tail.next = node;
    tail = node;
    size++;
  }

  public void add(int index, E value) {
    validateIndex(index, size);

    if (index == 0) {
      addFirst(value);
      return;
    }
    if (index == size) {
      add(value);
      return;
    }
    // 추가하려는 위치의 이전 노드
    Node<E> prevNode = searchNode(index-1);

    // 추가하려는 위치의 노드
    Node<E> nextNode = prevNode.next;

    // 추가하려는 노드
    Node<E> newNode = new Node<E>(value);

    prevNode.next = newNode;
    newNode.next = nextNode;
    size++;
  }

  private void addFirst(E value) {
    Node<E> node = new Node<E>(value);
    node.next = head;
    head = node;
    size++;
    if (head.next == null) {
      tail = head;
    }
    return;
  }

  public void delete(int index) {
    if (index == 0) {
      deleteFirst();
      return;
    }
    validateIndex(index, size);

    Node<E> prevNode = searchNode(index-1);
    Node<E> targetNode = prevNode.next;
    Node<E> nextNode = targetNode.next;

    prevNode.next = nextNode;
    targetNode.data = null;
    targetNode.next = null;
    size--;
  }

  private void deleteFirst() {
    if (head == null) {
      throw new NoSuchElementException();
    }
    Node<E> nextNode = head.next;
    head.data = null;
    head.next = null;
    head = nextNode;
    size--;
    if (size == 0) {
      tail = null;
    }
  }

  public E get(int index) {
    return searchNode(index).data;
  }

  public void set(int index, E value) {
    Node<E> node = searchNode(index);
    node.data = value;
  }

  public int size() {
    return size;
  }

  private void validateIndex(int index, int size) {
    if (index < 0 || index >= size) {
      throw new IndexOutOfBoundsException();
    }
  }
}

 

양방향 링크드리스트

import java.util.NoSuchElementException;

class Main {
  public static void main(String[] args) {
    doublyLinkedList<Integer> linkedList = new doublyLinkedList<>();
    linkedList.add(1);
    linkedList.add(2);
    linkedList.add(3);
    printElements(linkedList.size(), linkedList);  
  }

  public static void printElements(int size, doublyLinkedList<Integer> linkedList) {
    for (int i = 0; i < linkedList.size(); i++) {
      System.out.print(linkedList.get(i) + " ");
    }
    System.out.println();
  }
}

class Node<T> {
  T data;
  Node<T> prev;
  Node<T> next;

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

class doublyLinkedList<T> {
  private Node<T> head;
  private Node<T> tail;
  private int size;

  public doublyLinkedList() {
    this.head = null;
    this.tail = null;
    this.size = 0;
  }

  private Node<T> searchNode(int index) {
    validateIndex(index);
    Node<T> node;
    if (index > size / 2) {
      node = tail;
      for (int i = size - 1; i > index; i--) {
        node = node.prev;
      }
    } else {
      node = head;
      for (int i = 0 ; i < index; i++) {
        node = node.next;
      }
    }                                                                                  
    return node;
  }

  public void add(T value) {
    if (size == 0) {
      addFirst(value);
      return;
    }
    Node<T> newNode = new Node<T>(value);
    tail.next = newNode;
    newNode.prev = tail;
    tail = newNode;
    size++;
  }

  public void add(int index, T value) {
    if (size == 0) {
      addFirst(value);
      return;
    }
    if (size == index) {
      add(value);
      return;
    }
    Node<T> newNode = new Node<T>(value);
    Node<T> prevNode = searchNode(index-1);
    Node<T> nextNode = prevNode.next;

    prevNode.next = newNode;
    newNode.prev = prevNode;

    nextNode.prev = newNode;
    newNode.next = nextNode;
    size++;
  }
  
  private void addFirst(T value) {
    Node<T> newNode = new Node<T>(value);
    newNode.next = head;
    if (head != null) {
      head.prev = newNode;
    }
    head = newNode;
    size++;
    if (head.next == null) {
      tail = head;
    }
  }

  public void delete(int index) {
    validateIndex(index);
    if (index == 0) {
      deleteFirst();
      return;
    }
    
    Node<T> prevNode = searchNode(index-1);
    Node<T> targetNode = prevNode.next;
    Node<T> nextNode = targetNode.next;

    targetNode.prev = null;
    targetNode.next = null;
    targetNode.data = null;
    prevNode.next = null;

    if (nextNode != null) {
      prevNode.next = nextNode;
      nextNode.prev = prevNode;
    } else {
      tail = prevNode;
    }
    size--;
  }

  private void deleteFirst() {
    Node<T> headNode = head;

    if (headNode == null) {
      throw new NoSuchElementException();
    }
    Node<T> nextNode = head.next;

    head.data = null;
    head.next = null;

    if (nextNode != null) {
      nextNode.prev = null;
    }

    head = nextNode;
    size--;

    if (size == 0) {
      tail = null;
    }
  }

  public T get(int index) {
    return searchNode(index).data;
  }

  public void set(int index, T value) {
    Node<T> targetNode = searchNode(index);
    targetNode.data = value;
  }

  public int size() {
    return size;
  }

  private void validateIndex(int index) {
    if (index < 0 || index >= size) {
      throw new IndexOutOfBoundsException();
    }
  }
}