Queues and Linked Lists…


Again, we come back to different types of data structures. A Linked List is essentially a “chain” of sorts, you can add objects, delete objects, move objects; i.e. the list can grow or shrink to any size, removing the restrictions that an Array based implementation would have. Its one of the most used and known data structures. To illustrate even further:

Node Class:

class Node//this node class will be used for both the queue and linked list classes
    {
        public int data { get; set; }
        public Node next { get; set; }

        public Node(int data)
        {
            this.data = data;
            next = null;
        }
    }

Singly Linked List:

class LinkedList
{
  private Node first;
  private Node last;
  private int listCount = 0;

public LinkedList() { }
public void AddItem(int data)//we will pass in an integer to the AddItem function enter in the linkedlist
{
  Node newItem = new Node(data);
  if (first == null)
  {
    first = newItem;
    last = first;
  }
  else
  {
    Node traverse = first;
    while (traverse.next != null)//go through the linked list to find the last node of the list and add a pointer to the new item
    {
      traverse = traverse.next;
    }
    traverse.next = newItem;//adds the new item and makes the last part of the list point the new item
    last = traverse.next;
  }
 listCount++;
}
public void RemoveFirst()//we have RemoveFirst() function to remove the first node
{

   Node newFirst = first.next;//set a node to equal the next node in the list
   first = null;//set the current first node to equal null
   first = newFirst;//set the next node to be the first
   listCount--;
   DisplayList();
}
public void RemoveLast()//we also have a RemoveLast() function to remove the last node
{

  int index = 1;
  //if we are removing from the back, traverse the list until the last node = traversal and set to null
  Node traversal = first;
  while (traversal.next != null)
  {
    traversal = traversal.next;
    index++;
    if (index == listCount - 1)
    {
       break;
        //break from the loop when the index reaches length-1
        //we do this so that the penultimate item in the list becomes the new last node
    }
  }
  last = traversal;//set last to equal the current traversal node (penultimate)
  traversal.next = null;//set the next node to null
  listCount--;//decrement the number of items inside the list
  DisplayList();//re-write the list
}
public void RemoveItem(int removeValue)
{//the RemoveItem function takes an int parameter, so that it finds something to delete

//to remove an item...
//traverse the list
//set a node called nextnext
//assign the nextnext to the current traversal node.next.next
//it looks like this:
//node->current->next->nextnext
//if we delete a middle node
//we look to the next nodes data
//if it checks out, set to null
//set the current node.next (traversal) to nextnext
//it will link the current traversal node to nextnext
//like so: A->B->tranversal(current)->traversal.next (middle)->traversal.next.next (nextnext)
//becomes: A->B->Current->nextnext

  Node traversal = first;//a node to traverse the list
  Node nextnext = null;
  while (traversal.next != null)
  {
    nextnext = traversal.next.next;
    if (traversal.next.data == removeValue)
    {
      traversal.next = null;
      traversal.next = nextnext;
      break;
    }
    else
    {
      traversal = traversal.next;
    }
  }

  listCount--;//decrement the number of list items
  DisplayList();//re-write the list
}
public void DisplayList()
{
    Node current = first;
    while (current != null)
    {
      Console.WriteLine("{0} ", current.data);
      current = current.next;

       if (current == null)
       {
         return;
       }
    }
}
}


The same goes for a Queue. A Queue is like a Stack, however, its based on a First In First Out algorithm. So if add an object called “numberOne” to a queue, and I add another object called “numberX”, when I go to DeQueue(which to take an object out of the queue), the first object that will DeQueue is “numberOne”.

We can create a Queue when we are “using System.Collections;” by simply typing: Queue nameOfQueue = new Queue();

If we wanted to do a manual implementation of a Queue using Linked Lists, here is my version of the data structure…

Queue:

class Queue
{
   private Node head;
   private Node end;
   private int itemCount = 0;
   public Queue() { head = end = null;}

  public void Enqueue(int data)//we add an item to the back of the queue
  {
    Node n = new Node(data);
    if (head == null)//if theres nothing in the first place, we make the new node both the head and end of the queue
    {
       head = n;
       end = head;
    }
    else
    {
      end.next = n;
      end = end.next;
    }
    itemCount++;
  }
  public int Dequeue()//we will return the first value that was enqueued in the queue
  {
     if (head == null)
     {
         throw new IndexOutOfRangeException(); //if theres no head of in the queue
     }
     else
     {
         Node tmp = head;
         int val = tmp.data;
         head = head.next;
         tmp = null;
         itemCount--;
         return val;
     }
  }
 public void DisplayQueue()//to display the items of the queue in order, we dequeue and write
 {//this function also tests our Dequeuing function
    int i = 0;
    while (i <= itemCount)
    {
       Console.Write("{0} ", Dequeue());
       if (i == itemCount)
       {
         break;
       }
    }
 }
}

Finally, we have whats called a Doubly Linked List that has two pointers,a next and a previous. Illustrated here below:

doublelinkedlist

Implementation in C#:

class Doubly_LinkedList
    {
        class DLL_Node
        {
            public int data;
            public DLL_Node previous;
            public DLL_Node next;
            public DLL_Node(int data)
            { this.data = data; }
        }
        DLL_Node first;
        DLL_Node last;
        public Doubly_LinkedList()
        {

        }
        public bool IsEmpty()
        {
            if (first == null)
            {
                return true;
            }
            else { return false; }
        }
        public void Add(int data)
        {
            DLL_Node newItem = new DLL_Node(data);
            if (IsEmpty() == true)
            {
                first = newItem;
                last = newItem;
            }
            else
            {
                newItem.previous = last;
                last.next = newItem;
                last = newItem;
            }
        }
        public void PrintForward()
        {
            DLL_Node current = first;
            while (current != null)
            {
                Console.Write("{0} ", current.data);
                current = current.next;
            }
        }
        public void PrintReverse()
        {
            DLL_Node current = last;
            while(current != null)
            {
                Console.Write("{0} ", current.data);
                current = current.previous;
            }
        }
        public bool Find(int target)
        {
            DLL_Node current = first;
            bool isFound = false;
            while (current != null)
            {
                if (current.data == target)
                {
                    isFound = true;
                    break;
                }
                else { current = current.next; }
            }
            return isFound;
        }
        public void Delete(int target)
        {
            if (target == first.data)
            { DeleteFirst(); }
            if (target == last.data)
            { DeleteLast(); }
            else
            {
                DLL_Node current = first;
                while (current != null)
                {
                    if (current.next.data == target)
                    {
                        current.next.next.previous = current;
                        current.next = current.next.next;
                        break;
                    }
                    else { current = current.next; }
                }
            }
        }
        private void DeleteFirst()
        {
            first = first.next;
            first.previous = null;
        }
        private void DeleteLast()
        {
            last = last.previous;
            last.next = null;
        }
    }

In terms of time complexity, the queue, singly and doubly linked list, all have worst and average cases of O(n). For their best case, it is O(1).

Advertisements

4 thoughts on “Queues and Linked Lists…

  1. Pingback: Hash Tables tutorial (C#, C++, Java) | Bits and Pieces of Code

  2. Pingback: AVL Tree in C# | Bits and Pieces of Code

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s