双向链表代码,C代码库,德仔网

代码语言

代码分类

【C】双向链表

作者:littleDog / 发布于2015/6/10/ 520


	#ifndef DOUBLY_LINKED_LIST
	#define DOUBLY_LINKED_LIST
	
	template<class T>
	class DLLNode {
	public:
	 DLLNode() {
	 next = prev = 0;
	 }
	 DLLNode(const T& el, DLLNode<T> *n = 0, DLLNode<T> *p = 0) {
	 info = el; next = n; prev = p;
	 }
	 T info;
	 DLLNode<T> *next, *prev;
	};
	
	template<class T>
	class DoublyLinkedList {
	public:
	 DoublyLinkedList() {
	 head = tail = 0;
	 }
	 void addToDLLTail(const T&);
	 T deleteFromDLLTail();
	 ~DoublyLinkedList() {
	 clear();
	 }
	 bool isEmpty() const {
	 return head == 0;
	 }
	 void clear();
	 void setToNull() {
	 head = tail = 0;
	 }
	 void addToDLLHead(const T&);
	 T deleteFromDLLHead();
	 T& firstEl();
	 T* find(const T&) const;
	protected:
	 DLLNode<T> *head, *tail;
	 friend ostream& operator<<(ostream& out, const DoublyLinkedList<T>& dll) {
	 for (DLLNode<T> *tmp = dll.head; tmp != 0; tmp = tmp->next)
	 out << tmp->info << ' ';
	 return out;
	 }
	};
	
	template<class T>
	void DoublyLinkedList<T>::addToDLLHead(const T& el) {
	 if (head != 0) {
	 head = new DLLNode<T>(el,head,0);
	 head->next->prev = head;
	 }
	 else head = tail = new DLLNode<T>(el);
	}
	
	template<class T>
	void DoublyLinkedList<T>::addToDLLTail(const T& el) {
	 if (tail != 0) {
	 tail = new DLLNode<T>(el,0,tail);
	 tail->prev->next = tail;
	 }
	 else head = tail = new DLLNode<T>(el);
	}
	
	template<class T>
	T DoublyLinkedList<T>::deleteFromDLLHead() {
	 T el = head->info;
	 if (head == tail) { // if only one DLLNode on the list;
	 delete head;
	 head = tail = 0;
	 }
	 else { // if more than one DLLNode in the list;
	 head = head->next;
	 delete head->prev;
	 head->prev = 0;
	 }
	 return el;
	}
	
	template<class T>
	T DoublyLinkedList<T>::deleteFromDLLTail() {
	 T el = tail->info;
	 if (head == tail) { // if only one DLLNode on the list;
	 delete head;
	 head = tail = 0;
	 }
	 else { // if more than one DLLNode in the list;
	 tail = tail->prev;
	 delete tail->next;
	 tail->next = 0;
	 }
	 return el;
	}
	
	template <class T>
	T* DoublyLinkedList<T>::find(const T& el) const {
	 DLLNode<T> *tmp = head;
	 for ( ; tmp != 0 && !(tmp->info == el); // overloaded ==
	 tmp = tmp->next);
	 if (tmp == 0)
	 return 0;
	 else return &tmp->info;
	}
	
	template<class T>
	T& DoublyLinkedList<T>::firstEl() {
	 return head->info;
	}
	
	template<class T>
	void DoublyLinkedList<T>::clear() {
	 for (DLLNode<T> *tmp; head != 0; ) {
	 tmp = head;
	 head = head->next;
	 delete tmp;
	 }
	}
	
	#endif

评论列表

本站所提供的代码，版权归原作者所有，若有侵犯作者版权，请与我们联系，我们将立即删除或修改。谢谢!
本站所有代码发布及提供者。

试试其它关键字

　双向链表　

同语言下

可能有用的

littleDog贡献的其它代码(3)