Leave a comment

Understanding Linked List

We need data structure while writing the program. Doesn’t matter if it is a small program or a complex application, but you need data structures to hold your data so that you can process the data whenever required. Each data structure as its own pros and cons. For an example, in array you have direct access to each element so, you can access element in constant time but the problem with array is you need to declare the size of the array in prior and you cannot store more elements than the size of the array. Size is required at the time of declaration of the array itself because that many contiguous blocks of memory will be allocated to this array and that is the reason you have direct access to each element.

Let’s not get into the array as it is diverting from the original topic. But yeah! if you want to know how direct access works, please let me know, I will be more than happy to explain. So the main point is you need you need to declare the size of the array and in turns you should know the size of data you are going to hold in array in advance. Prior knowledge of the size of data is sometime very difficult. You can consider a simple scenario where you are taking input from user at runtime.

As I told, each data structure has its own pros and cons, each data structure is made for different purpose and it is best for some particular situation. For example, if you already know the size of data and you have no requirement of insertion and deletion of the data in middle, array is best. If data is associated with a key and you need to do operation like search, insert and delete on the basis of key, hashtable is best and so on.
Likewise, Link List is a data structure best suit for the situation where you do not have any idea about the size of the data. It is basically different blocks of data in memory, linked together. Those blocks of data are not at contiguous location, they can reside anywhere in memory. Each block has address to its next block.

For example Link List of 1 2 3 4 5 can be represented in memory like shown below:

linklist

It is just a representation of link list in memory. You can see that 1 has 2 as its next, stored somewhere in memory. 1 will be having the address of the memory location where 2 is stored in and 2 will be having the address of memory location where 3 is stored and so on. That is what those links shown in above are about. Last not will not have any next address and that field will be null for this node.
So the structure of the node of linklist will have two fields, one is data and another is next address which will point to the next node in link list.

Now let’s say if you have to store 6 after 5, what needs to e done? Following operation needs to be executed.

  1. Store 6 somewhere in memory and have its address
  2. Traverse till last node from head of the link list. Remember, you do not have direct access to the nodes in link list, head (which is 1 in this case) is the one you can access and after that you need to traverse the list using next address to reach at certain node.
  3. Assign address of node 6 to the next address field of node 5.

This way our list grows and you can see that no prior knowledge of size of data is required. As soon as data comes you can add it to the link list.
You can observe that insertion and deletion of node is also very easy. Just a matter of changing next addresses of the node involved.
For example, you want to insert 7 after 4, you will traverse till 4, next address of 4 will be assigned to next address of 7 and whatever is the address of 7, will be assigned to next address of 4 and 7 is now in between 4 and 5.

By performing a similar sequence of operations we can delete node.

I am giving a simple implementation for understanding, find it herein below:

public class LinkList {
    private int data;
    private LinkList next;
    public LinkList(int data) {
        super();
        this.data = data;
    }
    public int getData() {
        return data;
    }
    public void setData(int data) {
        this.data = data;
    }
    public LinkList getNext() {
        return next;
    }
    public void setNext(LinkList next) {
        this.next = next;
    }
}


public class LinkListUtils {
    public static LinkList insert(LinkList head, int val){
        LinkList node = new LinkList(val);
        if(head == null){
            head = node;
        }else{
            LinkList temp = head;
            // traversing till last node, only last node will have null as next address
            while(temp.getNext() != null){
                temp = temp.getNext();
            }
            temp.setNext(node);
        }
        return head;
    }
}

Above explained list is called singly link list as you can start from head and can traverse in one direction. There is one more link list called Doubly Link List which I will cover in some later post.

Looking forward to hear your query if any.

Advertisements

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

%d bloggers like this: