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:

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).

nice

LikeLike

Saved as a favorite, I love your site!

LikeLike

[…] chaining: all keys that map to the same hash value are kept in a linked list (or bucket). It does has its drawbacks, while it is a good way to resolve collisions, it has […]

LikeLike

[…] tree. We know that in the worst case retrieval and insertion is O(n), when the tree looks like a linked list, and traversal is pretty much like that of a linked list. This is quite inefficient and costs time. […]

LikeLike