[자료구조] Vectors, Lists, Sequences ADT

Vector (array list) 

cf. python에는 array를 대신해서 array list가 들어가있다. 좀 더 유저 친화적인 High-level array ADT이다.

 

벡터 ADT가 가진 함수들(배열과 유사함) :

• at(i) : V(벡터)의 i번째 요소 return. i가 범위를 벗어날 경우 에러 발생
• set(i, e) : i번째 요소를 e로 바꾼다. i가 범위를 벗어날 경우 에러 발생
• insert(i, e) : V의 i번째에 새로운 요소 e를 삽입한다. i가 범위를 벗어날 경우 에러 발생
• erase(i) : V의 i번째 요소를 지운다. i가 범위를 벗어날 경우 에러 발생

---

복습 

Array에서 insert, erase(add, remove) : O(n)

                    space used by the data structure : O(n)

                    indexing the element at i : O(1)

 

insert & erase pseudo-code 

---

Vector Performance

Operation	Time
size()	O(1)
empty()	O(1)
at(i)	O(1)
set(i, e)	O(1)
insert(i, e)	O(n)
erase(i)	O(n)

---

ArrayVector : reserve and insert 함수

pseudo-code 작성

---

 

Lists

 We would like to define functions for the linked-lists(vector : array) that take nodes of the list as parameters and provide nodes as return types.

(node를 반환)

 

But, 유저에게 node의 직접적인 접근을 허용하는 것은 좋지 않다.

*노드에 대한 접근을 간접화하기 위하여 position 개념이 도입된다.(유저의 간접적 접근 허용)

 

→ Perspective of Object-oriented design principles of abstraction and encapsulation

(OPP 입장에서 굉장히 중요한 개념)

---

Position

• an abstract data type that is associated with a particular container and which supports the following function.

→ element() 함수 : Return a reference to the element stored at this position. ( in c++, *p ; in python, p.element() )

→ 노드의 접근과 이동을 담당하는 iterator : supports the ability to access a node's element, but it also provides the ability to navigate forwards (and possibly backwards) through the container. ( ex : .next, ++ )

 

List ADT의 함수

• begin() : Return an iterator referring to the first element of L(return header->next)
• end() : Return an iterator referring to an imaginary element just after the last element(return trailer)
• insertFront(e) : 앞에 새로운 요소 추가
• insertBack(e) : 뒤에 추가
• insert(p, e) : p의 위치의 앞에 e 추가
• eraseFront() : 맨 앞에 요소 지움
• eraseBack() : 맨 뒤의 요소 지움
• erase(p) : p의 자리 지움

 

---

Sequence

 일반화된 ADT → worst time complexity

 

 supports all the functions of the list ADT, but also provides functions for accessing elements by the index, as we did in the vector ADT

 

• atIndex(i) : Return the position of the element at index i.
• indexOf(p) : Return the index of the element at position p.

 

---

코드

class NodeSequence : public NodeList{
public:
	iterator atIndex(int i) const;
    int indexOf(const Iterator& p) const;
}