Menü

C++ üzerinde Çift Bağlı Liste Uygulaması

18 Kasım 2017 - c++, veri yapilari
C++ üzerinde Çift Bağlı Liste Uygulaması

Okuldaki bir ödevim için kodladığım çift bağlı liste (doubly linked list) kodum.

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

Bir cevap yazın

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir

This site uses Akismet to reduce spam. Learn how your comment data is processed.