DataStructure

[자료구조] Lists

식빵민 2022. 4. 17. 18:52
  • 객체가 자료구조 속 어디 저장 되어있는지에 대한 위치 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;
    }