Linked List

Basic Concept of Singly Linked List

    Lets start with a game. You have been given the name of a person who lives in a particular address. But you don't know the person. There will be multiple other person on the way who knows the address of next person only. So how will you reach to the proper person who's name has been given to you? (Provided none of your helpers is liar). It's not a big deal. You will start your journey and ask a person for his name and if the name is same with the given name then you have found him otherwise you will ask for the address of next person and so on. Finally you will get to the person if the person really exists. If you got this far then I will say that you just learned the basic concept of linked list.

    Yes you are right. Linked list is nothing but a sequence of nodes that contains the value and the address of the next node. The final node will contain the value and a NULL address that points to nothing.

    In the above pic the 1^st node contains Data = A and Address of next node(i.e. contains item B) = X

    2^nd node contains Data = B and Address of next node(i.e.  contains item C) = Y

    3^rd node contains Data = C and Address of next node(i.e.  contains item D) = Z

    4^th node contains Data = D and Address = NULL that points to nothing. Its end of the linked list.

    So, this one of the important data structures in computer science.

    Now what are the properties that we have got so far from the description of linked?

    Please validate the points :

    1. It's linear (i.e. one dimensional).

    2. Each node contains the data and an address to the next node which is similar to next node unless it reaches to it's last node.

    3. We can't access any node directly. We have to come across all the preceding nodes. i.e. sequential access is needed.

    Now you need a place on the street for each people in our game. Same is applicable here also, you need primary memory addresses to keep the data and address in nodes. We can add or remove as many people as we want on the street at random places during the game to test your patient, we really don't need to worry about specifying number of people on the street. Likewise during run time the linked list will automatically allocate memory to it for creating new nodes. So another feature comes from this discussion.

    4. Linked list is dynamic data structure which allocates the needed memory at the run time.

    5. Insertion and deletion of data in a node is easy.

    6. Incontiguous memory allocation.

    Now what if I tell you to go back to your initial position after you got the given person. Difficult ! Yeah little bit. So add another point based on the discussion so far.

    7. Traversing backward is difficult for linked list.