DataStructure
[자료구조] Lists
식빵민
2022. 4. 17. 18:52
- 객체가 자료구조 속 어디 저장 되어있는지에 대한 위치 ADT
- position의 개념 이용
- 배열의 셀
- 링크드 리스트의 노드
- 단일 함수
- p.element() : element의 위치를 반환
c++에서 p는 포인터, p는 주소값을 가진다.
- p.element() : element의 위치를 반환
- 반복자
- begin() : 가장 앞에 position 반환
- end(): 가장 뒤에 position 반환
- 속성 함수
- size() : List의 크기 반환
- empty() : List가 비어있는 지 판단
- 업데이트 함수
- insertFront(e) : 가장 앞에 노드 추가
insetBack(e) : 가장 뒤에 노드 추가 - removeFront() : 가장 앞에 있는 노드 삭제
removeBack() : 가장 뒤에 있는 노드 삭제
- insertFront(e) : 가장 앞에 노드 추가
- 반복자를 활용한 업데이트 함수
- 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; }