In our everyday life we encounter list: creating a list for a day-to-day task, a list for our favorite songs and name in our phonebooks. In this sample tutorial we will look at one particular type of list, the linked list. A.Net framework contains list-based collection classes, but linked list was not considered as part of the framework library. These tutorials will explain to you why linked list is needed in the program, a sample code of an object based linked list and array-based linked list.
How Arrays described?
Array is considered as the simplest form of data structure when storing multiple data in your program. Insertion and retrieving of data can be done easily by just specifying its index when invoking an array. Array is already part of the language so it does not require extra memory and processing time when it is used in the program.
Major drawbacks of Arrays
Common drawbacks in using static arrays are that, it lacks the flexibility to handle data that grows dynamically during runtime, searching of elements in unsorted array element is dawdling or slow for it has possibly visits the entire element in the array. Addition and deletion of elements is quite difficult for it has to shift the elements to avoid errors.
What is Linked List?
A linked list is a collection of class objects called nodes that have the characteristic to grow and shrink during runtime. Each node is linked to its successor node in the list using a reference to the successor node. A node is made up of a field for storing data and the field for the node reference. The reference to another node is called a link.
Comparing Linked list to an Array
A major difference between an array and a linked list is that the elements of a linked list are referenced by their relationship to the other elements of the array, whereas the elements in an array are referenced by position (the index).
AN OBJECT-ORIENTED LINKED LIST
In designing an Object-Oriented linked list involves at least two classes: A Node class and a node object instantiated to a Node Class each time we add a node to the list. The nodes in the list are connected via references to other nodes through an element called pointer which holds the address of the next node object. These references are set using methods created in a separate Linked List class.
Element of a Node Class
A Node Class is consists of different elements or fields these are: Data field and Pointer or address field. A Data field holds the actual data of a Node object while pointer field holds the address node of the next node object in the list. Purpose of this is to link the nodes in a list.
This is what linked list look like after inserting values (21-24).
This example will show you how it is done, just copy and past the source code on your program.Here’s a sample code of a node class. (Filename: Node.cs)
using System;
namespace LinkedListSample{
class Node
{
private Node _next;
private object _data;
public Node()
{
_next = null;
}
public Node next
{
get
{
return _next;
}
set
{
_next = value;
}
}
public object data
{
get
{
return _data;
}
set
{
_data = value;
}
}
}
}
Single Linked List Class (Filename: SLL.cs)
using System;
using System.Collections;
namespace LinkedListSample{
public class SingleLinkedList
{
private Node head;
private Node tracer;
public SingleLinkedList()
{
head = null;
tracer = null;
}
public void insertNode(object data)
{
if(head==null)
{
head = new Node();
tracer = head;
head.data = data;
}
else
{
Node tempNode = new Node();
tempNode.data = data;
tracer.next = tempNode;
tracer = tempNode;
}
}
public void deleteNode(object data)
{
Node temp;
temp = head;
if(head.data.ToString() == data.ToString())
{
head = head.next;
temp = head;
}
else
{
while(temp != null && temp.next != null)
{
if(temp.next.data.ToString() == data.ToString())
{
temp.next = temp.next.next;
if(temp.next == null)
{
tracer = temp;
}
}
temp = temp.next;
}
}
}
public void traverse()
{
Node temp = head;
while (temp != null)
{
Console.Write(temp.data + " ");
temp = temp.next;
}
}
}
}
Linked List Implementation. (Filename: Main.cs)
using System;
namespace LinkedListSample{
class Program
{
public static void Main(string[] args)
{
// TODO: Implement Functionality Here
SingleLinkedList list = new SingleLinkedList();
int data=0;
Console.WriteLine("Insert node: 21, 22, 23, 24, 25 ");
list.insertNode(21);
list.insertNode(22);
list.insertNode(23);
list.insertNode(24);
list.insertNode(25);
list.insertNode(27);
Console.WriteLine("Output after insertion: ");
list.traverse();
Console.WriteLine("\n\nDelete Node 24: ");
Console.WriteLine("Output after deletion: ");
list.deleteNode(24);
list.traverse();
Console.WriteLine("\n\nDelete Node 22: ");
Console.WriteLine("Output after deletion: ");
list.deleteNode(22);
list.traverse();
Console.WriteLine("\n\nInsert node: 26 ");
list.insertNode(26);
Console.WriteLine("Output after insertion: ");
list.traverse();
Console.WriteLine("\n");
}
}
}
Subscribe to:
Post Comments (Atom)
0 comments for this post