ADT

Abstract Data Type

• A mathematical model of the data objects that make up a data type as well as the functions that operate on these objects.
• Defined indirectly, by the operations that may be performed on it and by mathematical constraints on the effects of those operations.
• It is composed of
  • A data structure
  • A set of operation of the types of the methods (called a signature)
  • A precise description of the types of the methods (called a signature)
  • A precise set of rules about how it behaves (called the abstract specification or the axiomatic description)
  • An implementation hidden from the programer

---

ArrayList ADT

Definition

• 임의의 객체들의 연속을 저장한다.
• 인덱스를 통해 접근, 삽입, 삭제가 가능하다.
• 잘못된 인덱스에 접근하면 exception 발생.

Main methods

• get(integer i) - O(1)
• set(integer i, object o) - O(1)
• add(integer i, object o) - O(n) when i = 0
• remove(integer i) - O(n) when i = 0

Additional methods

• size() - O(1)
• isEmpty() - O(1)

Growable Array-based ArrayList

• When the array is full in an add operation

1. 예외 처리
2. replace the array with a larger one
   • Incremental strategy : 상수만큼 증가
   • Doubling strategy : 사이즈 2배씩 증가

Amortized time : T(n) / n

• 여러번의 연산을 평균냈을 때 한 연산당 걸리는 시간.
• append는 O(n)이라 느려보이지만, 실제로 대부분 O(1)만 걸리는 연산이 대부분.

---

Linked Lists ADT

Definition

• 노드들의 연속으로 이루어져 있다.
• 각 노드는 데이터와 다른 노드들과의 연결 정보를 갖고 있다.

Properties

• 스택, 큐를 구현할 때 사용될 수 있다.
• 기존 구조에서 큰 변화 없이 쉽게 삽입, 삭제가 가능하다.
• 어느 위치에서는 constant time 안에 삽입, 삭제가 가능하다.
• 특정 데이터에 접근하기 위해서는 traversal process가 불가피하다.
• Array에 비해 구조적으로 flexible하지만, 특정 데이터 접근은 오래걸린다.
• Tail에서 Node를 제거하는 것은 constant time안에 해결할 수 없다. 왜냐, tail에서 이전 노드를 가리키도록 하는 메소드가 존재하지 않기 때문이다.
• 따라서 Singly Linked List에서는 tail 근처에서 노드를 제거하는 것은 바람직하지 않다.

---

NodeList ADT

Definition

• 임의의 객체들을 저장하는 위치들의 연속을 model한다.
• 위치별 앞, 뒤 관계를 설정한다.
• DLL : Doubly Linked List -> NodeList ADT를 자연스럽게 구현할 수 있도록 해준다. 양방향 관계를 갖고 있다.

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)

Algorithms

• Insertion

Alg insertAfter(p, e):
	Create a new node v
    v.setElement(e)
    v.setPrev(p)
    v.setNext(p.getNext())
    p.getNext().setPrev(v)
    p.setNext(v)
    return v

• Deletion

Alg remove(p):
	t = p.element
    p.getPrev().setNext(p.getNext())
    p.getNext().setPrev(p.getPrev())
    p.setPrev(null)
    p.setNext(null)
    return t

Stack, Queue as a LL

Stack

• top(head)에서만 계속 add, pop을 해주면 된다.
  • space : O(n)
  • Time complexity of each operation : O(1)

Queue

• We can implement a queue with a singly linked list
  • The front element is stored at the first node.
  • The rear element is stored at the last node.
• Complexity of the QueueADT
  • Space complexity: O(n)
  • Time complexity of each operation : O(1)

---

Stack ADT

Definition

• top에서만 모든 삽입, 삭제가 이뤄지는 ordered list.

Properties

• LIFO scheme
• Typically implemented with array or linked list.

Methods

Main

• push(Object)
• Object pop()

Others

• Object top()
• int size()
• boolean isEmpty()

Common Applications of Stack

• 웹 브라우저 방문 기록
• text editor의 undo
• 괄호 매칭
• 수식 계산

Array based Stack

Performance

• when the number of elements is n,
• Space complexity : O(n)
• Time complexity of all operations : O(1)

Limitations

• 스택 사이즈가 array 특성상 의해 미리 선언되어야 하며, 바뀔 수 없다.
• 풀스택에 새 원소를 넣으면 예외 발생. 따라서 growable array 전략을 사용해야 한다.