[Vector/List]18. Position ADT, List ADT

목차

1. Position ADT

2. List ADT

3. Doubly Linked List

4. Performance

 

1. Position ADT

 Position ADT(위치)은 특정 data 구조가 저장되어있는 위치를 알아내는 ADT입니다. 이는 특정 array의 cell, 혹은 linked list의 node의 주소를 알고싶을 때, 주로 사용됩니다. 주요 기능은 p.element()입니다.

 

2. List ADT

 List ADT는 임의의 데이터를 저장하는 ADT입니다.

 

1) 특징

- List ADT는 2가지 특징을 지니고 있다.

- element의 위치를 지정해야 함

- 특정 위치의 앞과 뒤의 element에 access할 수 있어야 함

 

2) 기능들

- size(): list의 크기를 반환한다.

- empty(): list가 비었는지 여부를 반환한다.

- begin(), end(): 시작, 끝 값을 반환한다ㅏ.

- insertFront(e), insertBack(e): 앞, 혹은 뒤에 새로운 element e를 넣는다.

- eraseFront(), eraseBack(): 앞, 혹은 뒤에 element를 삭제한다.

- insert(p, e): index p의 자리에 새로운 element e를 넣는다.

- erase(p): index p의 자리에 있던 element를 삭제한다.

 

3. Doubly Linked List

 List ADT를 구현하는 방법 중, Double Linked List(이중 연결 리스트)를 사용할 수 있습니다. Double Linked List은 전에 언급했던 Singly Linked List와 다르게, 각각 element를 저장하고 있는 node가 이전, 그리고 다음 node의 주소값을 저장한다는 것이 특징입니다.

 

4. Performance

- n개의 element를 지니고 있는 List ADT에 소요되는 메모리 공간은 O(n)이다.

- 각각 list의 element를 저장하는 데 필요한 메모리 값은 O(1)이다.

- List ADT의 모든 기능들은 O(1)시간이 소모된다.

- 주의할 점: LIst ADT에는 index를 통한 탐색만 있을 뿐, element의 값을 통한 탐색은 없다.

- 따라서, 따로 찾는 방법을 만들어야 한다.