In an array, elements are physically stored in consecutive places. Since we know element number x will be available in the place A+X-1, where A is the starting location of the array, accessing elements is very faster one-by-one or randomly. But, think about rearranging these numbers. In order to place an element between two other numbers, we have to make a place empty between them. It is very tedious to move the entire elements to subsequent places to make a room for the new number. Deletion is also the same kind of job, when we delete the element the space should be moved to the end of array where all remaining spaces are.

If you could think of allocating more elements to an existing array, or discarding unused places by leaving them to some other variables, then it’s impossible with arrays. Once if you decide to use array you should also decide its permanent size.

To overcome this problem, we need a special data structure called linked list. While using linked list memory for each element is allocated on demand, in other words dynamic memory allocation. Building blocks of a linked list are called list nodes. Each node will have a same structure to hold the data as well as the address to the next node in the list sequence. Following figure demonstrates the structure of a list node,

List Node

Initially if the list is empty, we will only be having the place to keep an address of any node and that is called header pointer. Once the node is created the element will be copied in the data part of the list node and address of that node will be in the header pointer. The link part of the node will be initially having the null value representing node nodes are available further. If the next node comes we have to decide whether that should be kept as a first element or the second one. If it is going to be the second element, then we will copy the address of the new node into the link part of the first node so that when we start from the header pointer, we will go to first node and then do whatever we want to do with the data at the first node, get the address of the second node and so on.

The following is the class for list node.

public class ListNode
{
    public Name Data;
    public ListNode Link;
    public ListNode()
    {
        Link=null;
    }
}

There are two different properties in the class declared as public members. This means the members can be accessed from its instances. This constructor initializes the Link initially be empty when the node is being created.

Various operations performed on linked lists

• Create a list
• Insert an item at front
• Insert an item as a last one
• Insert an item after another value which is already in the list
• Insert an item before another value in the list
• Traverse ( Get the items in an array or as a comma seperated items in a string)
• Remove an item from the list
• Make a list empty (Delete the list)

Next we have to implement the linked list in the following pseudo class by defining methods for performing the above specified operations.

public class LinkedList
{
    private ListNode Head;
    public LinkedList();
    public Boolean InsertAtFront(int Value);
    public Boolean InsertAtLast(int Value);
    public Boolean InsertAfter(int Value, int ExistingValue);
    public Boolean InsertBefore(int Value, int ExistingValue);
    public string GetItemsInString();
    public string[] GetItemsInArray();
    public Remove(int Value);
    public Reverse();
    ~LinkedList();
}

To be continued in Part 2…