Diff: CircularLinkedList.h

Revision:

0:fe8decc6a938

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/CircularLinkedList.h	Thu Mar 29 09:26:14 2012 +0000
@@ -0,0 +1,161 @@
+
+/*  A circular double linked list
+  *  
+  * Copyright (c) 2012 Bart Janssens
+  *
+  * Permission is hereby granted, free of charge, to any person obtaining a copy
+  * of this software and associated documentation files (the "Software"), to deal
+  * in the Software without restriction, including without limitation the rights
+  * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+  * copies of the Software, and to permit persons to whom the Software is
+  * furnished to do so, subject to the following conditions:
+  *
+  * The above copyright notice and this permission notice shall be included in
+  * all copies or substantial portions of the Software.
+  *
+  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+  * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
+  * THE SOFTWARE.
+  */
+template <typename T>
+class Node
+{
+public:  
+  Node(T data) : data(data), next(NULL) {}
+//private:
+  Node *next;
+  Node *prev;
+  T data;  
+};
+
+template <typename T>
+class CircularLinkedList
+{
+public:
+  CircularLinkedList() : head(NULL),size(0) {}  //constructor
+  ~CircularLinkedList(); // decunstructor
+  bool isEmpty() { return (head == NULL);}  // is list Empty ?
+  void moveForward(); // move cursor forward
+  void moveBackward(); // move cursor backward
+  void toHead(); // move cursor to head
+  T * getNode();
+  void addNode(T data);
+  void deleteNode(T data);
+  int getSize();
+private:
+  Node<T> *head;
+  Node<T> *cursor;
+  int size;
+};
+
+template <typename T>
+CircularLinkedList<T>::~CircularLinkedList()
+{
+  if (!isEmpty()) {
+      Node<T> *tmp = head;
+      while (tmp->next != head) {
+          Node<T> *t = tmp;
+          tmp = tmp->next;
+          delete(t);
+      }
+      delete tmp;
+      head = NULL;
+  }
+}
+
+
+
+template <typename T>
+T * CircularLinkedList<T>::getNode()
+{
+  return &(cursor->data);
+}
+
+template <typename T>
+void CircularLinkedList<T>::addNode(T data)
+{
+  Node<T> * t = new Node<T>(data);
+
+  if (isEmpty())
+    {
+      t->next = t;
+      t->prev = t;
+      head = t;
+      size++;
+      cursor = head;
+      return;
+    }
+
+  Node<T> *tmp = head;
+  while (tmp->next !=  head)
+    {
+      tmp = tmp->next;
+    }
+
+  tmp->next = t;
+  t->next = head;
+  t->prev = tmp;
+  head->prev = t;
+  size++;
+}
+
+template <typename T>
+void CircularLinkedList<T>::deleteNode(T data)
+{
+  Node<T> *tmp = head;
+  Node<T> *prev = NULL;
+  while (tmp->next !=  head)
+    {
+      if (tmp->data == data) break;
+      prev = tmp;
+      tmp = tmp->next;
+    }
+
+  if (tmp == head)
+    {
+      while (tmp->next != head)
+        {
+          tmp = tmp->next;
+        }
+      tmp->next = head->next;
+      head->next->prev = tmp
+      delete head;
+      size--;
+      head = tmp->next;
+    }
+  else
+    {
+      prev->next = tmp->next;
+      tmp->next->prev = prev;
+      delete tmp;
+      size--;
+    }
+}
+
+template <typename T>
+void CircularLinkedList<T>::moveForward()
+{
+    if (!isEmpty()) cursor = cursor->next;
+}
+
+template <typename T>
+void CircularLinkedList<T>::moveBackward()
+{
+    if (!isEmpty()) cursor = cursor->prev;
+}
+
+template <typename T>
+void CircularLinkedList<T>::toHead()
+{
+    cursor = head;
+}
+
+template <typename T>
+int CircularLinkedList<T>::getSize()
+{
+    return size;
+}
\ No newline at end of file