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;
}
}
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<Type> nameOfQueue = new Queue<Type>();
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
{
int val = head.data;
head = head.next;
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;
}
}
}
}
