DS Lec.5 - Linked Lists

Linked Lists

• 데이터와 다음 노드를 가리키는 정보를 갖고 있다.
• Properties
  - 스택, 큐같은 ADT를 구현할 때 사용될 수 있다.
  - 삽입, 삭제시 Array처럼 reallocate나 전체 구조를 reorganization할 필요 없이 O(1), constant time에 수행 가능하다. 즉, Array보다 훨씬 flexible하다.
  - 단, random access to the data는 불가하다.
  - 맨 끝 값의 next는 null을 가리킨다.

  Array vs Linked List

  장점

  Array는 삽입, 삭제시에 O(n)의 worst case가 존재하지만, LL은 둘 다 constant time만에 수행 가능하다. 즉, Array보다 더 flexible하다고 표현한다.

  단점

  Array는 index로 O(1)만에 접근이 가능하지만, LL는 어떤 노드를 찾기 위해서는 첫 노드에서 해당 값까지 순회해야 한다. 따라서 random access를 allow 하지 않는다.

Removing a Node at the Tail

• There's no constant time way to make the tail to point to the previous node.
• So, removing at the tail of a singly linked list is not efficient.

  Array와 같은 '연속적인 자료구조'에서는 우측(끝)에서 삽입, 삭제가 이뤄지는 것이 최선이지만, Singly Linked List에서는 비효율적이다!

NodeList ADT

• it models a sequence of positions storing arbitrary objects.
• Methods
  • Generic : size(), isEmpty()
  • Accessor : first(), last(), prev(p), next(p)
  • Modifier : set(p, e), addBefore(p, e), addAfter(p, e), addFirst(e), addLast(e), remove(p)

Doubly Linked List

• NodeList ADT를 '구현한' Data Structure
• NodeList ADT의 연산들을 효율적으로 구현하기 위한 자료구조 중 하나.
• Methods
  • Generic : p.size() ...
  • Accessor : p.getHead(), p.getTail, p.prev(), p.next()
  • Modifier : p.set(p, e), p.addBefore(p, e), ...
• 각 노드들은 아래 3가지 정보들을 저장한다.
  • Element, Link to the prev node, Link to the next node
• Special trailer and header nodes
  • 초기에 head나 tail이 null이거나, 연산 중간에 null인 상황이 발생할 수 있다.
  • 이 때, 이런 null 검증을 없앰으로서 편의성을 증가시키기 위해 header at head, trailer at tail 노드들을 양 끝 단에 위치시키고, 항상 그 사이에서만 노드의 편집이 일어나도록 놔둔 것.

public DoublyLinkedList() {
        header = new Node<>(null, null, null);
        trailer = new Node<>(null, header, null);
        header.next = trailer;
        size = 0;
    }

위처럼 선언하고, 나머지 노드 편집은 사이에서 일어나게 조절하면 끝.

Stack as a Linked List

• LIFO 구현
  • SLL로 충분히 구현 가능하다.
  • SLL의 head를 스택에서의 top 역할로 맡기면 끝. 즉, SLL의 첫 번째 노드를 top으로 규정하면 된다.
  • head에서만 계속 삽입, 삭제를 하면 된다.
  • 공간복잡도 : O(n)
  • 시간복잡도 of each operations : O(1)

Queue as a Linked List

• FIFO 구현
  - SLL로 충분히 구현 가능하다.
  - 첫 번째 노드(head)에 front 원소 저장
  - 마지막 노드(tail)에 rear 원소 저장
  - 공간복잡도 : O(n)
  - 시간복잡도 of each operations : O(1)

  Tail node는 SLL과 DLL 둘 다 가질 수 있는 것인가?

  • 그렇다. DLL과 SLL의 개념적 차이는 prev가 있냐 없냐에 달렸기 때문에, tail 노드의 구현 여부는 상관 없다.
  • 그래서 SLL로도 큐를 구현할 수 있다는 것.
    SLL에서도 'rear에서의 삭제'가 tail의 앞 노드를 찾아야 하기 때문에 비효율적이라고 했지, 삽입은 구현 가능하다.
    그러므로 head 삭제, tail 삽입은 매우 가능.

  public void enqueue(Object e) {
      Node v = new Node(e, null); // 새 노드 (next = null)
      if (isEmpty()) {
          head = v;
          tail = v;
      } else {
          tail.setNext(v);
          tail = v;
      }
      size++;
  }
  
  public Object dequeue() {
      if (isEmpty()) throw new NoSuchElementException();
      Object elem = head.getElement();
      head = head.getNext();
      size--;
      if (isEmpty()) tail = null; // 마지막 노드 뺐을 때 tail도 null 처리
      return elem;
  }