Okuldaki bir ödevim için kodladığım çift bağlı liste (doubly linked list) kodum.
#ifndef _LINKEDLIST_H_ #define _LINKEDLIST_H_ #include <iostream> #include <cstddef> #include <stdexcept> #include <iomanip> using namespace std; template<class T> class Node; template<class T> ostream &operator<<(ostream &out, const Node<T>& n); /* node class for linked list */ template<class T> class Node { private: Node<T> *prev; Node<T> *next; T data; public: /*** Do not modify the interface ***/ Node(); Node(const T& d); Node<T>* getNext() const; Node<T>* getPrev() const; T getData() const; T* getDataPtr(); void setNext(Node<T> *newNext); void setPrev(Node<T> *newPrev); void setData(const T& data); friend ostream &operator<< <> (ostream &out, const Node<T>& n); /*** Do not modify the interface ***/ }; /* TO-DO: method implementations here */ template<class T> Node<T>::Node(){ prev=next=NULL; } template<class T> Node<T>::Node(const T& d){ data = d; } template<class T> Node<T>* Node<T>::getNext() const{ return next; } template<class T> Node<T>* Node<T>::getPrev() const{ return prev; } template<class T> T Node<T>::getData() const{ return data; } template<class T> T* Node<T>::getDataPtr(){ return *data; } template<class T> void Node<T>::setNext(Node<T> *newNext){ next = newNext; //newNext->prev = this; } template<class T> void Node<T>::setPrev(Node<T> *newPrev){ prev = newPrev; //newPrev->next = this; } template<class T> void Node<T>::setData(const T& data){ this->data = data; } template<class T> ostream &operator<<(ostream &out, const Node<T>& n){ out << setfill('.') << setw(10) << (void*)n.prev <<" <-| "<< (void*)&n <<" |-> " << setfill('.') << setw(10) << (void*)n.next << " : " << n.data ; return out; }; template <class T> class LinkedList { private: /* pointer to the first node */ Node<T>* front; /* pointer to the last node */ Node<T>* back; public: /*** Do not modify the interface ***/ LinkedList(); LinkedList(const LinkedList<T>& ll); LinkedList<T>& operator=(const LinkedList<T>& ll); ~LinkedList(); /* returns the first node of the linked list */ Node<T>& getFront() const; /* returns the last node of the linked list */ Node<T>& getBack() const; /* returns the node in given "pos"ition of the linked list */ Node<T>& getNodeAt(int pos) const; /* returns the pointer of the node in given "pos"ition of the linked list */ Node<T>* getNodePtrAt(int pos) const; /* inserts a new node containing "data" after the node "prev" */ void insert(Node<T>* prev, const T& data); /* inserts a new node containing "data" at "pos"ition in the linked list */ void insertAt(int pos, const T& data); /* erases the given "node" from the linked list */ void erase(Node<T>* node); /* erases the node in given "pos"ition from the linked list */ void eraseFrom(int pos); /* clears the contents of the linked list */ void clear(); /* inserts a new node containing "data" to the front of the linked list */ void pushFront(const T& data); /* inserts a new node containing "data" to the back of the linked list */ void pushBack(const T& data); /* removes the first node */ void popFront(); /* removes the last node */ void popBack(); /* returns true if the list is empty, false otherwise */ bool isEmpty() const; /* returns the number of items in the list */ size_t getSize() const; /* prints the contents of the linked list one node data per line assumes the objects in the node have operator<< overloaded */ void print() const; /*** Do not modify the interface ***/ }; /* TO-DO: method implementations here */ template <class T> LinkedList<T>::LinkedList(){ front = NULL; back = NULL; } template <class T> LinkedList<T>::LinkedList(const LinkedList<T>& ll){ front = NULL; clear(); Node<T>* tmp = ll.getNodePtrAt(0); for(int i = 0; tmp != NULL; i++) { insertAt(i, tmp->getData()); tmp = tmp->getNext(); } } template <class T> LinkedList<T>& LinkedList<T>::operator=(const LinkedList<T>& ll){ front = NULL; clear(); Node<T>* tmp = ll.getNodePtrAt(0); for(int i = 0; tmp != NULL; i++) { insertAt(i, tmp->getData()); tmp = tmp->getNext(); } } template <class T> LinkedList<T>::~LinkedList(){ Node<T>* tmp = front; while(tmp!=NULL) { tmp->setPrev(NULL); Node<T>* nextt = tmp->getNext(); delete tmp; tmp = nextt; } front=NULL; back=NULL; } template <class T> Node<T>& LinkedList<T>::getFront() const{ return *front; } template <class T> Node<T>& LinkedList<T>::getBack() const{ return *back; } template <class T> Node<T>& LinkedList<T>::getNodeAt(int pos) const{ Node<T>* tmp; tmp = front; if(pos<0) throw domain_error("not possible"); for(int i=0;i<pos;i++){ if(tmp->getNext()==NULL) throw domain_error("not possible"); tmp=tmp->getNext(); } return *tmp; } template <class T> Node<T>* LinkedList<T>::getNodePtrAt(int pos) const{ Node<T>* tmp; tmp =front; for(int i=0;i<pos;i++){ tmp=tmp->getNext(); } return tmp; } template <class T> void LinkedList<T>::insert(Node<T>* prev, const T& data){ Node<T>* newNode = new Node<T>; newNode->setData(data); newNode->setNext(prev->getNext()); if(prev!=back) prev->getNext()->setPrev(newNode); else back=newNode; prev->setNext(newNode); newNode->setPrev(prev); } template <class T> void LinkedList<T>::insertAt(int pos, const T& data){ Node<T>* newNode = new Node<T>; int nullchecker=0; newNode->setData(data); if(front == NULL){ front = newNode; back = newNode; } else { Node<T>* tmp; tmp =front; for(int i=0;i<pos;i++){ if(tmp->getNext()!=NULL) tmp=tmp->getNext(); else nullchecker=1; } if(pos>getSize()){ back = newNode; } if(nullchecker!=1 and pos!=0){ newNode->setNext(tmp); newNode->setPrev(tmp->getPrev()); tmp->getPrev()->setNext(newNode); tmp->setPrev(newNode); } else if(pos!=0){ tmp->setNext(newNode); newNode->setPrev(tmp); newNode->setNext(NULL); } else { newNode->setNext(tmp); tmp->setPrev(newNode); newNode->setPrev(NULL); front = newNode; } } } template <class T> void LinkedList<T>::erase(Node<T>* node){ Node<T>* tmp; if ( node != front){ if(getSize()!=1){ tmp = node->getPrev(); if(node->getNext()!=NULL){ tmp->setNext(node->getNext()); node->getNext()->setPrev(tmp); } else { tmp->setNext(NULL); back=tmp; } } else { front = NULL; back = NULL; } delete node; } else { tmp = node->getNext(); tmp->setPrev(NULL); delete node; front = tmp; } } template <class T> void LinkedList<T>::eraseFrom(int pos){ Node<T>* tmp; Node<T>* prev; tmp =front; if ( pos !=0){ for(int i=0;i<pos;i++){ tmp=tmp->getNext(); } prev = tmp->getPrev(); if(tmp->getNext()!=NULL){ prev->setNext(tmp->getNext()); tmp->getNext()->setPrev(prev); } else{ prev->setNext(NULL); } delete tmp; } else { prev = tmp->getNext(); prev->setPrev(NULL); delete tmp; front = prev; } } template <class T> void LinkedList<T>::clear(){ while(front != NULL) popFront(); } template <class T> void LinkedList<T>::pushFront(const T& data){ Node<T>* newNode = new Node<T>; newNode->setData(data); if (front != NULL) { newNode->setNext(front); front->setPrev(newNode); front = newNode; front->setPrev(NULL); } else { front = newNode; front->setPrev(NULL); back = newNode; back->setNext(NULL); } } template <class T> void LinkedList<T>::pushBack(const T& data){ Node<T>* newNode = new Node<T>; newNode->setData(data); if(front==NULL){ front = newNode; front->setPrev(NULL); back = newNode; front->setNext(back); back->setNext(NULL); back->setPrev(front); } else if(back!=NULL){ newNode->setPrev(back); back->setNext(newNode); newNode->setNext(NULL); } back = newNode; } template <class T> void LinkedList<T>::popFront(){ Node<T>* tmp; if(front->getNext()!=NULL and back!=front){ tmp=front->getNext(); delete front; front = tmp; front->setPrev(NULL); } else { back = NULL; front = NULL; delete front; } } template <class T> void LinkedList<T>::popBack(){ Node<T>* tmp; tmp=back->getPrev(); tmp->setNext(back); delete back; back = tmp; back->setNext(NULL); } template <class T> bool LinkedList<T>::isEmpty() const{ if (front == NULL) return 1; else return 0; } template <class T> size_t LinkedList<T>::getSize() const{ Node<T>* tmp; size_t x; tmp = front; x=0; if (tmp!=NULL ){ while(tmp->getNext()!=NULL){ tmp=tmp->getNext(); x++; } x++; return x; } else return 0; } template <class T> void LinkedList<T>::print() const{ Node<T>* tmp; int i=0; tmp = front; if (front != NULL){ while(tmp->getNext()!=NULL or tmp->getNext()!=0){ i++; cout << tmp->getData() << endl; tmp = tmp->getNext(); } cout << tmp->getData() << endl; } } #endif