○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)
'컴퓨터 지식 > 자료구조' 카테고리의 다른 글
| Sequence (0) | 2020.11.20 |
|---|---|
| Iterator, Container (0) | 2020.11.06 |
| Array Lists(Vector) (0) | 2020.11.02 |
| Adapter (0) | 2020.10.28 |
| Deque (0) | 2020.10.28 |
