Position, Node List

○Position

 ▷위치를 나타내는 자료구조

 ▷하나의 object가 저장되어있음. (장소를 통해 object 접근)

 ▷ex) a cell of an array, a node of a linked list

 ▶메서드

  ▷object p.element(): position의 element(object)를 반환함.

   ▷C++에서 *p로 해석됨.

 

 

○Node List

 ▷데이터를 저장하는 Sequence of positions

 ▷position간의 앞/뒤 관계로 구성

 ▷Doubly Linked List와 거의 동일한 ADT

 

 ▶Method

  ▶iterators

   ▷begin(): 가장 앞의 position 반환.

   ▷end(): 가장 뒤의 position 뒤에 있는 가상의 position 반환.

  ▶Update methods

   ▷insertFront(e): 가장 앞에 해당 element를 가진 position 추가

   ▷insertBack(e): 가장 뒤에 해당 element를 가진 position 추가

   ▷removeFront(): 가장 앞의 position 제거

   ▷removeBack(): 가장 뒤의 position 제거

  ▶iterator-based update

   ▷insert(p, e): position p의 앞에 e를 가진 position 추가.

   ▷remove(p) : position p 제거.

  ▶Generic methods

   ▷size(): 

   ▷empty(): 

 

 ◎Doubly Linked List - Node List

  ▷거의 동일한 ADT이기 때문에 D.L.L 로 Node List를 만들 수 있다.

  ▷Insert(p,e)

  ▷remove(p)

 

  ▶성능

   ▷size, empty: O(n)

   ▷insert, remove: O(1)

   ▷element: O(1)