[자료구조] Lists

• 객체가 자료구조 속 어디 저장 되어있는지에 대한 위치 ADT
  • position의 개념 이용 
  • 배열의 셀
  • 링크드 리스트의 노드
• 단일 함수
  • p.element() : element의 위치를 반환
    c++에서 p는 포인터, p는 주소값을 가진다.
• 반복자
  • begin() : 가장 앞에 position 반환
  • end(): 가장 뒤에 position 반환
• 속성 함수
  • size() : List의 크기 반환
  • empty() : List가 비어있는 지 판단
• 업데이트 함수
  • insertFront(e) : 가장 앞에 노드 추가 
    insetBack(e) : 가장 뒤에 노드 추가
  • removeFront() : 가장 앞에 있는 노드 삭제
    removeBack() : 가장 뒤에 있는 노드 삭제
• 반복자를 활용한 업데이트 함수
  • insert(p,e) : p앞에 e 삽입
  • remove(p) : p에 있는 노드 삭제

 

• Doubly Linked List노드
  • next : 다음 노드를 가리키는 포인터. (노드의 구성요소 중 하나)
  • prev : 이전 노드를 가리키는 포인터. (노드의 구성요소 중 하나)
  • value : 해당 노드의 값
• Trailer : 가장 뒤에 있는 노드를 가리키는 노드.(값과 next는 없음)
• Header : 가장 앞에 있는 노드를 가리키는 노드.(값과 prev는 없음)

  #include <iostream>
  #include <string>
  
  using namespace std;
  
  class Node{
  public:
      Node* next = nullptr;
      Node* prev = nullptr;
      int data;
  };
  class DoublyLinkedList{
  private:
      Node* header = nullptr;
      Node* trailer = nullptr;
      int size = 0;
  public:
      DoublyLinkedList(){
          size = 0;
          header = new Node;//가장 앞에있는 원소의 다음 노드
          trailer = new Node;//가장 뒤에있는 원소의 이전 노드
          header->next = trailer;//초기에는 header와 trailer만 존재
          trailer->prev = header;
          header->prev = trailer->next = NULL;
      }
      int getSize(){return size;}
      bool empty(){return (getSize()==0);}
      Node* begin(){
          return header->next;//리스트의 첫 번째 원소의 주소를 반환
      }
      Node* end(){
          return trailer;//리스트의 마지막 원소의 다음 주소(trailer)를 반환
      }
      void insert(Node* pos, int data){//리스트의 pos가 가리키는 노드의 앞에 data 삽입
          Node* newNode = new Node;
          newNode->data = data;
          newNode->prev = pos->prev;
          newNode->next = pos;
          pos->prev->next = newNode;
          pos->prev = newNode;
          size++;
      }
      void insertFront(int data){
          insert(begin(),data);
      }
      void insertBack(int data){
          insert(end(),data);
      }
      void erase(Node* pos){
          pos->next->prev = pos->prev;
          pos->prev->next = pos->next;
          delete pos;
          size--;
      }
      void eraseFront(){
          erase(begin());
      }
      void eraseBack(){
          erase(end()->prev);
      }
  };
  int main(){
      int T;
      cin>>T;
      DoublyLinkedList list = DoublyLinkedList();
      Node* p = list.begin();//위치 노드 생성
      string cmd;
      while(T--){
          cin>>cmd;
          if(cmd=="size"){
              cout<<list.getSize()<<endl;
          }else if(cmd == "begin"){
              list.begin();
          }else if(cmd=="end"){
              list.end();
          }else if(cmd=="insert"){
              int x;
              cin>>x;
              list.insert(p,x);
              
          }else if(cmd=="erase"){
              list.erase(p);
              p = list.begin();
          }else if(cmd=="prevP"){
              if(p != list.begin())
              p = p->prev;//위치를 한칸 전으로
          }else if(cmd=="nextP"){
              if(p != list.end())
              p = p->next;//위치를 한칸 후로
          }
      }
      return 0;
  }