LinkedList(SinglyLinkedList vs DoublyLinkedList)

LinkedList

LinkedList란 Collection 프레임워크의 일부이며 java.util 패키지에 소속되어 있다. 이 클래스는 데이터가 연속된 위치에 저장되지 않고 모든 데이터가 데이터 영역과 주소 영역을 별도로 가지고 있스빈다. 데이터는 포인터와 주소를 사용하여 연결하고, 각 데이터는 노드라 불리며 배열에서 자주 삽입, 삭제가 이루어지는 경우 ArrayList 보다 선호된다.

LinkedList의 종류와 속성

위에서 말했듯 Node는 Data를 담을 수 있는 변수와 다른 Node를 참조하는 2개의 변수로 이루어져 있다. 그리고 LinkedList는 Node의 구성에 따라 싱글 링크드리스트(Single-LinkedList), 더블 링크드리스트(Double-LinkedList)로 구분할 수 있다.

Singly LinkedList
Doubly LinkedList

LinkedList의 세 가지 속성은 다음과 같다.

헤드(head): 연결 리스트의 시작 노드를 가리킨다.
테일(tail): 연결 리스트의 마지막 노드를 가리킨다. 중간에 있는 노드들은 일일이 추적하지 않는다.
크기(size): 작업을 용이하게 하기 위해서 사이즈라는 속성을 계속 유지한다.

Singly LinkedList

Singly LinkedList Diagram

HEAD Size: 4 TAIL
4 ---> 6 ---> 8 ---> 2 --->
next next next null

LinkedList는 위처럼 인덱스 주목할 수 있다! 즉, 무엇이 0번째이고, 첫 번째, 두 번째 그리고 세 번째 라는 식으로 이야기할 수 없다. 이 리스트에 무엇인가를 접근하고 싶다면 첫 번째 노드부터 시작해야 한다. LinkedList는 단지 다음 노드들을 가리키고 있는 수많은 노드들이라고 보면 된다.

Node

public class Node<T> {
	T data;
    Node<T> next; // 다음 노드객체를 가리키는 레퍼런스 변수
    
    Node(T data) {
    	this.data = data;
        this.next = null;
    }
}

Single LinkedList는 위 코드처럼 각 노드가 다음 노드를 가리키는 형태로 구성된다. Single LinkedList의 단점은 리스트를 순회할 때, 이전의 노드로 이동할 수 없기 때문에 단방향으로만 순회가 가능하다는 점이다. 이를 보완하기 위해서 고안된 것이 Double LinkedList이다.

Singly LinkedList

public class SinglyLinkedList<T> {

    private Node<T> head;
    private Node<T> tail;
    private int size;

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

    public Node<T> get(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException();
        }

        Node<T> node = head;

        // index만큼 count하여 index의 노드 찾기
        for (int count = 0; count < index; count++) {
            node = node.next;
        }

        return node;
    }

    public void unShift(T data) {
        Node<T> newNode = new Node<T>(data);

        if (size == 0) {
            addFirst(data);
            return;
        }

        newNode.next = head;
        head = newNode;
        size++;
    }

    public void add(T data) {
        // size가 0인 경우 head, tail이 첫 노드로 지정
        if (size == 0) {
            addFirst(data);
            return;
        }

        Node<T> newNode = new Node<>(data); // 마지막에 추가할 노드

        tail.next = newNode;
        tail = newNode;
        size++;
    }

    /**
     * data를 원하는 index 위치에 추가 -> O(n)
     */
    public void insert(int index, T data) {
        if (index > size || index < 0) {
            throw new IndexOutOfBoundsException();
        }

        // 0번 인덱스에 추가하려는 경우에는 unShift 메서드로 추가 -> O(1)
        if (index == 0) {
            unShift(data);
            return;
        }

        // 마지막 인덱스에 노드 추가하려는 경우에는 append 메서드로 추가 -> O(1)
        if (index == size) {
            add(data);
            return;
        }

        // 그 외에는 인덱스만큼 돌아 원하는 index에 추가 -> O(n)
        Node<T> newNode = new Node<>(data);
        Node<T> prevNode = get(index - 1);
        newNode.next = prevNode.next.next;
        prevNode.next = newNode;
        size++;
    }

    public boolean remove(T data) {
        Node<T> findNode = head;
        Node<T> prevNode = null;

        while (findNode.next != null) {
            if (findNode.data.equals(data)) {
                break;
            }

            prevNode = findNode;
            findNode = findNode.next;
        }

        if (findNode == null) {
            return false;
        }

        if (findNode.equals(head)) {
            Node<T> nextNode = head.next;
            head.next = null;
            head.data = null;
            size--;
            head = nextNode;
            return true;
        }
        
        prevNode.next = findNode.next;
        findNode.data = null;
        findNode.next = null;
        size--;
        return true;
    }

    public void clear() {
        Node<T> node = head;

        while (node.next != null) {
            node = node.next;
            node.data = null;
            node.next = null;
        }
        head.data = null;
        head.next = null;
        head = tail = null;
        size = 0;
    }

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * 헤드 및 테일 모두 처음 들어온 새로운 노드를 가리키도록 설정
     */
    private void addFirst(T data) {
        head = new Node<>(data);
        tail = head;
        size++;
    }

}

Big O of Singly LinkedList

삽입(Insertion): O(1)
삭제(Removal): O(1) or O(n)
- 리스트의 맨 마지막에서 노드를 제거하는 것은 Singly LinkedList head에서 출발해서 tail 앞에 있는 노드까지 찾아야 하기 때문에 최대 O(n)이 걸릴 수 있다.
탐색(Searching): O(n)
접근(Access): O(n)
- 검색이나 인덱스 접근 작업은 사이즈가 길어질수록 그에 비례해서 증가한다.
단방향 연결리스트는 삽입과 삭제의 경우 배열에 비해 우수하다.
- 따라서, 삽입 혹은 삭제 작업을 주로 해야 한다거나, 임의 접근 작업이 필요없으면서 주어진 순서대로 데이터를 관리할 필요가 있는 경우, 배열 보다는 단방향 연결리스트가 적절하다고 할 수 있다.

Doubly LinkedList

Doubly LinkedList Diagram

HEAD Length: 4 TAIL
null prev prev prev
<--- <--- <--- <---
4 6 8 2
---> ---> ---> --->
next next next null

Doubly LinkedList는 Singly LinkedList에서 추가로 뒤를 가리키는 포인터가 있다! 하지만 Singly LinkedList에 비해 메모리가 많이 든다는 단점이 있다.(More Flexibility에는 More Memory가 따른다..)

Node

public class Node<T> {
	public T data;
    Node<T> prev = null;
    Node<T> next = null;
}

더블 링크드리스트는 Node 내의 2개의 참조 변수가 이전과 다음 Node를 가리키는 형태로 구성된다.

Doubly LinkedList

public class DoublyLinkedList<T> {

  private Node<T> head;
  private Node<T> tail;
  private int size;

  public Node<T> get(int index) {
    if (index < 0 || index >= size) {
      throw new IndexOutOfBoundsException();
    }

    // index + 1이 크기의 절반 보다 크면 tail에서 시작, 아니면 head에서 시작
    if (index + 1 > size / 2) {
      Node<T> node = tail;

      for (int i = size - 1; i > index; i++) {
        node = node.prev;
      }

      return node;
    } else {
      Node<T> node = head;

      for (int i = 0; i < index; i++) {
        node = node.next;
      }

      return node;
    }
  }

  public void unShift(T data) {
    if (size == 0) {
      addFirst(data);
      return;
    }

    Node<T> newNode = new Node<>(data);
    head.prev = newNode;
    newNode.next = head;
    size++;
  }

  public void add(T data) {
    if (size == 0) {
      addFirst(data);
      return;
    }

    Node<T> newNode = new Node<>(data);
    tail.next = newNode;
    newNode.prev = tail;
    tail = newNode;
    size++;
  }

  public void insert(int index, T data) {
    if (index < 0 || index > size) {
      throw new IndexOutOfBoundsException();
    }

    if (index == 0) {
      unShift(data);
      return;
    }

    if (index == size) {
      add(data);
      return;
    }

    Node<T> newNode = new Node<>(data);
    Node<T> prevNode = get(index - 1);
    newNode.next = prevNode.next.next;
    newNode.prev = prevNode;
    prevNode.next = newNode;
    newNode.next.prev = newNode;
    size++;
  }

  public boolean remove(T data) {
    Node<T> findNode = head;
    Node<T> prevNode = head;

    while (findNode.next != null) {
      if (findNode.data.equals(data)) {
        break;
      }

      prevNode = findNode;
      findNode = findNode.next;
    }

    if (findNode == null) {
      return false;
    }

    if (findNode.equals(head)) {
      Node<T> nextNode = head.next;
      head.next = null;
      head.data = null;
      size--;
      head = nextNode;
      nextNode.prev = null;
      return true;
    }
    
    prevNode.next = findNode.next;
    findNode.next.prev = prevNode;
    findNode.data = null;
    findNode.next = null;
    findNode.prev = null;
    size--;
    return true;
  }
  
  public void clear() {
    Node<T> node = head;

    while (node.next != null) {
      node = node.next;
      node.data = null;
      node.next = null;
      node.prev = null;
    }
    head.data = null;
    head.next = null;
    head.prev = null;
    size = 0;
  }
  
  public int size() {
    return size;
  }
  
  public boolean isEmpty() {
    return size == 0;
  }

  private void addFirst(T data) {
    Node<T> newNode = new Node<>(data);
    head = tail = newNode;
    size++;
  }
}

Big O of Doubly LinkedList

삽입(Insertion) - O(1)
삭제(Removal) - O(1)
탐색(Searching) - O(n)
접근(Access) - O(n)
- 검색 및 접근하는데 Singly LinkedList에 비해 O(n / 2) 시간이 걸리지만, 이를 여전히 O(n)이라 표현한다.

출처

[JAVA] LinkedList의 개념 및 사용법

[자료구조/Java] LinkedList - 조회/추가/삭제 코드구현

깃헙 TIL - oneny

저작자표시

'기타 > 자료구조' 카테고리의 다른 글

Hash란? Java로 HashTable 구현하기 (0)	2023.08.31

자바시작 워니

LinkedList(SinglyLinkedList vs DoublyLinkedList)

LinkedList

LinkedList의 종류와 속성

Singly LinkedList

Singly LinkedList Diagram

Node

Singly LinkedList

Big O of Singly LinkedList

Doubly LinkedList

Doubly LinkedList Diagram

Node

Doubly LinkedList

Big O of Doubly LinkedList

출처

'기타 > 자료구조' 카테고리의 다른 글

티스토리툴바

LinkedList(SinglyLinkedList vs DoublyLinkedList)

LinkedList

LinkedList의 종류와 속성

Singly LinkedList

Singly LinkedList Diagram

Node

Singly LinkedList

Big O of Singly LinkedList

Doubly LinkedList

Doubly LinkedList Diagram

Node

Doubly LinkedList

Big O of Doubly LinkedList

출처

'기타 > 자료구조' 카테고리의 다른 글

관련글

티스토리툴바