[자료구조] Vectors, Lists, Sequences

Vectors

• Vector or array list
  -> 보통 python에서는 Vector보다 Array list를 많이 사용하고 Array list가 좀 더 High-level ADT로 유저 친화적
• ADT가 제공하는 함수
  • at(i) : index i에 있는 V의 원소를 리턴, 파라미터 i가 범위 밖으로 벗어나면 error
  • set(i,e) : index i에 있는 원소를 e로 대체, 파라미터 i가 범위 밖으로 벗어나면 error 바꾸기
  • insert(i,e) : index i에 e를 넣는데, index i 이후 원소들은 모두 오른쪽으로 밀고 빈자리에 e를 삽입,
                  파라미터 i가 범위 밖으로 벗어나면 error 오른쪽으로 밀기
  • erase(i) : index i에 있는 원소를 지움, 파라미터 i가 범위 밖으로 벗어나면 error
• Example

Operation	Output	V
insert(0,7)	-	(7)
insert(0,4)	-	(4,7)
at(1)	7	(4,7)
insert(2,2)	-	(4,7,2)
at(3)	error	(4,7,2)
erase(1)	-	(4,2)
insert(1,5)	-	(4, 5, 2)
insert(1,3)	-	(4, 3, 5, 2)
set(3, 8)	-	(4, 3, 5, 8)

• Pseudocode
  • Insert

    

    Insert는 이런식으로 오른쪽으로 밀고 새로운 원소를 삽입해준다. (방 만드는 느낌)

Algorithm insert(i, e): //i는 index, e는 element
	for j = n-1, n-2, ... , i do
    	A[j+1] = A[j] //j번째 있는 원소를 j+1번째에 넣는다.
    A[i] = e // 빈 자리에 새로운 원소 e를 넣는다.
    n = n + 1 //n은 사이즈, 삽입했으므로 사이즈 1 늘린다.

• erase
  메꾸는 느낌 (삭제할 인덱스에 덮어씌운다.)

Algorithm erase(i):
	for j = i+1, i+2, ..., n-1 do 
    	A[j-1] = A[j] // j번째 원소를 j-1번째 넣어준다.
    n = n - 1 // erase 했으므로 사이즈를 하나 줄인다.

 

• Time Complexity (Big-O Notation)

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)

 

• 기존보다 capacity가 더 큰 Arry를 위한 코드

void ArrayVector::reserve(int N) { //최소 N 사이즈
	if(capacity >= N) return; //이미 충분히 크므로 이 함수를 실행할 필요X
    Elem* B = new Elem[N};  //B는 더 큰 Array 만듦
    for(int j = 0; j < n; j++)
    	B[j] = A[j]  //A의 원소를 새로운 Array B에 값 복사
    if(A != NULL) delete[] A; // discard old array
    A = B; //A를 B와 완전히 똑같게 만들어줌
    capacity = N; //사이즈 = 용량
}

void ArrayVector::insert(int i, const Elem& e){
	if(n >= capacity) //사이즈가 capacity보다 크거나 같으면, capacity 더 필요함
    	reserve(max(1,2*capacity)) //capacity 더 할당(double strategy)
        
    for (int j = n-1; j>= i; j--)
    	A[j+1] = A[j]; // j번째 원소를 j+1번째에 넣어줌
    A[i] = e; // 빈 공간인 index i에 원소 e 넣어줌
    n++; //원소 추가했으므로 사이즈 1 늘리기
}

더 큰 용량을 할당하려고 하고 이를 reserve 함수로 구현했다. 한마디로 capacity를 늘리는 것인데 용량이라고 생각하면 된다. capacity를 늘리는 방법에는 incremental과 doubly 방법이 있는데 여기서는 doubly 방법을 이용했다.

(이 방법들이 궁금하다면 https://dkan9634.tistory.com/25?category=1006585 참고하면 좋을 것 같다.)

 

---

Lists

• Linked-Lists는 노드를 파라미터에서 받고 노드를 리턴한다. 이러한 점은 유저에게 Node의 직접적인 접근을 허용한다는 뜻이고 element도 직접 접근 할 수 있다. 따라서 노드에 대한 접근을 간접화 시키기 위해 사용하는 ADT가 List
• index 기반 기능에 비해 상당한 속도 제공
• 추상화 및 캡슐화(abstraction and encapsulation)의 OOP의 관점
• Position
  • List의 ADT는 특정한 container와 관련있다. (container란? elements 저장)
  • element() : 이 position에 저장된 element의 reference 리턴
    => C++에서 *p나 p.element()로 p가 지정하고 있는 노드의 데이터에 접근할 수 있다. (사용자의 간접 접근을 위해)
         기존에는?  node.element
  • iterator : node의 원소에 접근이 가능하도록 지원, container를 통해 앞이나 뒤로 탐색할 수 있는 기능을 제공
                       ex) .next, ++
    

    

• List ADT가 제공하는 함수
  • begin() : List의 첫번째 element  리턴
  • end() : List 마지막에 있는 원소의 다음인 가상의 원소 리턴 즉, 맨 마지막의 바로 다음 원소 리턴
  • insertFront(e) : Front에 e라는 원소 insert
  • insertBack(e) : Back에 e라는 원소 insert
  • insert(p,e) : position p 전에 새로운 원소 e 추가
  • eraseFront() : 맨 앞 원소 제거
  • eraseBack() : 맨 뒤 원소 제거
  • erase(p) : position p 에 있는 원소 제거
• Examples

Operation	Output	L
insertFront(8)	-	(8)
p = begin()	p : (8)	(8)
insertBack(5)	-	(8, 5)
q = p; ++q	q : (5)	(8, 5)
p == begin()	true	(8, 5)
insert(q, 3)	-	(8, 3, 5)
*q = 7	-	(8, 3, 7)
insertFront(9)	-	(9, 8, 3, 7)
erase(p)	-	(9, 3, 7)

 

• List 구현 코드
  

  //**************************iterator 구현************************
  class Iterator{
  public:
  	Elem& operator*();
      bool operator == (const Itrator& p) const;  //compare positions
      bool operator != (const Iterator& p) const;
      Iterator& operator++();  //move to next position
      Iterator& operatr--();	//move to previous position
      friend class NodeList;
  private:
  	Node* v;  //pointer to the Node
      Iterator(Node* u); // create from node
  }
  
  NodeList::Iterator::Iterator(Node* u)  //생성자
  	{ v = u; }
  
  Elem& NodeList::Iterator::operator*()  //reference to the element
  	{ return v->elem }
      
  bool NodeList::Iterator::operator==(const Iterator& p) const
  	{ return v == p.v; }
  
      
  bool NodeList::Iterator::operator!=(const Iterator& p) const
  	{ return v != p.v; }
  
  NodeList::Iterator& NodeList::iterator::operator++() //move to next position
  	{ v = v->next; return *this }
      
  NodeList::Iterator& NodeList::iterator::operator--() //move to previous position
  	{ v = v->prev; return *this }    
      
      
      
  //*************************NodeList 구현**************************
  NodeList::NodeList(){
  	n = 0; //initially empty
      header = new Node;
      trailer = new Node;
      header -> next = trailer;
      trailer -> prev = header;
  }
  
  int NodeList::size() const 
  	{ return n; } 
  
  bool NodeList::empty() const
  	{ return (n == 0); }
     
  NodeList::Iterator NodeList::begin() const
  	{ return Iterator(header->next); }
  
  NodeList::Iterator NodeList::end() const
  	{ return Iterator(trailer); }
  
  void NodeList::NodeList(){
  	n = 0; //initially empty
      header = new Node;
      trailer = new Node;
      header -> next = trailer;
      trailer -> prev = header;
  }
  
  int NodeList::size() const 
  	{ return n; } 
  
  bool NodeList::empty() const
  	{ return (n == 0); }
     
  NodeList::Iterator NodeList::begin() const
  	{ return Iterator(header->next); }
  
  NodeList::Iterator NodeList::end() const
  	{ return Iterator(trailer); }
      
   void NodeList::NodeList(){
  	n = 0; //initially empty
      header = new Node;
      trailer = new Node;
      header -> next = trailer;
      trailer -> prev = header;
  }
  
  int NodeList::size() const 
  	{ return n; } 
  
  bool NodeList::empty() const
  	{ return (n == 0); }
     
  NodeList::Iterator NodeList::begin() const 
  	{ return Iterator(header->next); }
  
  NodeList::Iterator NodeList::end() const //end position is just beyond last
  	{ return Iterator(trailer); }
      
  void NodeList::insert(const NodeList::Iterator& p, const Elem& e){ //insert e before p
  	//p 전에 e를 원소를 가지는 노드 추가
      Node* w = p.v; //p의 노드
      Node* u = w ->prev;  //p의 이전 노드
      Node* v = new Node;  //삽입할 새로운 노드
      
      v-> elem = e;
      v->next = w; w->prev = v;
      v->prev = u; u->next = v;
      n++;  //삽입했으므로 사이즈 1 증가
  }
  
  void NodeList::insertFront (const Elem& e){
  	return(begin(), e); }
      
  void NodeList::insertBack (const Elem& e){
  	return (end(), e);  }
      
  void NodeList::erase(const Iterator & p){
  	Node* v = p.v;   // p의 노드
      Node * w = v -> next;  
      Node* u = v -> prev;
      u->next = w; w->prev = u;
      delete v;
      n--;  // 삭제했으므로 사이즈 1 감소
  }
  
  void NodeList::eraseFront(){
  	erase(begin()); }
  
  void NodeList::eraseBack(){
  	erase(--end()); }  //end()가 가리키는 것은 맨 마지막 원소의 다음 원소이기 때문

---

Sequences

• 모든 List ADT 함수 지원하고 Vector ADT처럼 index 기반 접근도 가능
• 제일 일반화 시킨 ADT
• 단점 : 일반화 시켰기 때문에 상대적으로 성능 손해
• functions
  • atIndex(i) : Return the position of the element at index i
                   -> index i의 원소의 position 리턴
  • indexOf(p) : Return the index of the element at position p
                    -> position p 원소의 index 리턴
• Code

class NodeSequence : public NodeList {
public:
	Iterator atIndex(int i) const;  //get position from index
    int indexOf(const iterator& p) const; //get index from position
}

NodeSequence::Iterator NodeSequence::atIndex(int i) const{
	Iterator p = begin();
    for (int j = 0; j < i; j++)
    	++p;
    return p;
}

int NodeSequence::indexOf(const Iterator& p) const {
	Iterator q = begin();
    int j = 0; //index
    while(q != p){
    	++q; ++j;    
    }
    return j;
}

=> 시간 복잡도는 O(n)

 

 

틀린 부분은 댓글로 남겨주시면 감사하겠습니다.