/* Ajith - Syntax Higlighter - End ----------------------------------------------- */

8.26.2009

Implementation of Singly Linked List

This article is part of article series - "Datastructures"

Generally a Linked List means "Singly Linked List". It is a chain of records known as Nodes. Each node has at least two members, one of which points to the next Node in the list and the other holds the data.

Figure 1: Singly Linked List
Basically Single Linked Lists are uni-directional as they can only point to the next Node in the list but not to the previous. We use below structure for a Node in our example.
 struct Node
 {
   int Data;
   struct Node *Next;
 }; 
Variable Data holds the data in the Node (It can be a pointer variable pointing to the dynamically allocated memory) while Next holds the address to the next Node in the list.

Figure 2: Node in a Singly Linked List
Head is a pointer variable of type struct Node which acts as the Head to the list. Initially we set 'Head' as NULL which means list is empty.

Basic Operations on a Singly Linked List
  • Traversing a List
  • Inserting a Node in the List
  • Deleting a Node from the List

Traversing a Singly Linked List
Traversing a Singly Linked List is the basic operation we should know before we do other operations like Inserting a Node or Deletion of a Node from the Singly Linked List. Let us see how to traverse Singly Linked List in Figure 1.Let us assume Head points to the first Node in the List.

Pseudocode:
cur = head

forever:

if cur == NULL
break

cur = cur->Next
Complexity:
To traverse a complete list of size 'n' it takes
  • Time complexity: O(n).
  • Space Complexity: O(1) for storing one temporary variable.

Inserting a Node in Singly Linked List
There are 3 possible cases for inserting a Node in a Singly Linked List.

  • Inserting a Node at the beginning of the List

    In this case newNode is inserted at the starting of the List. We have to update Next in newNode to point to the previous firstNode and also update Head to point to newNode.

    Pseudocode:
    firstNode = Head->Next
    
    newNode->Next = firstNode
    
    Head->Next = newNode
    But above pseudocode can be modified to reduce the space complexity by removing the temporary variable usage as shown below
    newNode->Next = Head->Next
    
    Head->Next = newNode
    Complexity:
    Time Complexity: O(1)
    Space Complexity: None

    Sourcecode:
    void addBeg(int num)
     {
        struct Node *temp;
    
        temp=(struct Node *)malloc(sizeof(struct Node));
        temp->Data = num;
    
        if (Head == NULL)
        {
           //List is Empty
           Head=temp;
           Head->Next=NULL;
        }
        else
        {
           temp->Next=Head;
           Head=temp;
        }
     }

  • Inserting a Node at the End of the List

    In order to add the node at the end of the list we have to first traverse to the end of the List. Then we have to update the Next variable in lastNode pointing to newNode.

    Pseudocode:
    cur = head
    
    forever:
    
     if cur->Next == NULL
     break
    
    cur->Next = newNode
    Complexity:
    To add a Node at the end of a list whose length is 'n'

    Time Complexity: O(n)
    Space Complexity: O(1)

    Sourcecode:
    void addEnd(int num)
     {
        struct Node *temp1, *temp2;
    
        temp1=(struct Node *)malloc(sizeof(struct Node));
        temp1->Data=num;
    
        // Copying the Head location into another node.
        temp2=Head;
    
        if(Head == NULL)
        {
           // If List is empty we create First Node.
           Head=temp1;
           Head->Next=NULL;
        }
        else
        {
           // Traverse down to end of the list.
           while(temp2->Next != NULL)
           temp2=temp2->Next;
    
           // Append at the end of the list.
           temp1->Next=NULL;
           temp2->Next=temp1;
        }
     }

  • Inserting a Node at position 'p' in the List

    To add at the position 'p' we have to traverse the list until we reach the position 'p'. For this case have to maintain two pointers namely prevNode and curNode. Since Singly Linked Lists are uni-directional we have to maintain the information about previous Node in prevNode. Once we reach the position 'p' we have to modify prevNode Next pointing to newNode while newNode points to curNode.

    Pseudocode:
    curNode = head
    curPos = 1
    
    forever:
    
     if curPos == P || curNode == NULL
     break
    
     prevNode = curNode
     curNode = curNode->Next
     curPos++
    
    if curNode != NULL:
     
     prevNode->Next = newNode
     newNode->Next = curNode
    Complexity:
    Time Complexity: O(n) in worst case.
    Space Complexity: O(3)

    Sourcecode:
    void addAt(int num, int loc)
     {
        int i;
        struct Node *temp, *prev_ptr, *cur_ptr;
    
        cur_ptr=Head;
    
        if(loc > (length()+1) || loc <= 0)
        {
           printf("\nInsertion at given location is not possible\n ");
        }
        else
        {
            // If the location is starting of the list
            if (loc == 1)
            {
                addBeg(num);
            }
            else
            {
                for(i=1;i<loc;i++)
                {
                    prev_ptr=cur_ptr;   
                    cur_ptr=cur_ptr->Next;
                }
    
                temp=(struct Node *)malloc(sizeof(struct Node));
                temp->Data=num;
    
                prev_ptr->Next=temp;
                temp->Next=cur_ptr;
            }
        }
     }
    
     // Counting number of elements in the List
    
     int length()
     {
        struct Node *cur_ptr;
        int count=0;
    
        cur_ptr=Head;
    
        while(cur_ptr != NULL)
        {
           cur_ptr=cur_ptr->Next;
           count++;
        }
        return(count);
     }
Next Article: Deleting a Node from a Singly Linked List

119 comments :

  1. This program helped me better understanding Linked Lists.. Thank you very much.

    ReplyDelete
  2. Thanks for posting an example.

    ReplyDelete
  3. very good example to understand the singly link list concept

    ReplyDelete
  4. thank u verrrrrrrrrrryy much..... post like these simple programs withcomments....

    ReplyDelete
  5. Thanks a lot for posting the code. Very clear and clean code. Good Job.

    ReplyDelete
  6. it's useful for everyone...very great amazing........

    ReplyDelete
  7. thanks a lot posting this example.........

    ReplyDelete
  8. Thanks for posting these codes. It helped me a lot to understand Linked List. Good job! God bless. =)

    ReplyDelete
  9. it really very help 4 my subject thanx

    ReplyDelete
  10. easy to understand step wise

    ReplyDelete
  11. it helped me a lot...thank u very much

    ReplyDelete
  12. it helped me a lot...thank u very much

    ReplyDelete
  13. simply easy to understand....ty:)

    ReplyDelete
  14. very good explanation and indeed veru helful!! i bookmarked your blog.. thanks for your contribution

    ReplyDelete
  15. really helpful...thank you so much

    ReplyDelete
  16. I was totally confused about linked lists and the set of codes set it out all clear to me in a very simple manner. Kudos to the person for his efforts to bring out things in a lucid manner to all.

    ReplyDelete
  17. Wow! Thanks a lot :-)

    ReplyDelete
  18. Iterators help to make the list API even easier to use and more portable. A really simple reliable linked list in C that uses iterators is at https://launchpad.net/rlist

    ReplyDelete
  19. gr8 post mate... really good job!

    ReplyDelete
  20. superb!!!!!!!!!!!!
    simple and easier to understand

    ReplyDelete
  21. While most of it works I dont get why the while loop to find the end of the list has become a nightmare. Its become some infinite loop i cant fix.

    ReplyDelete
  22. simple and easy to understand.......

    ReplyDelete
  23. it is really nice i found myself very lucky to study this topic very well explained .......

    ReplyDelete
  24. This is very simple and interesting and it is awesome......

    ReplyDelete
  25. Perfect Explanation. Even most of our faculty are not mature enough to give such explanation.

    ReplyDelete
  26. nice work thanks

    ReplyDelete
  27. nice one dude. simple to understand

    ReplyDelete
  28. Really very very informative.. great

    -Demom

    ReplyDelete
  29. really helpful thanks for the blog

    ReplyDelete
  30. Really helpful thanks for the blog

    ReplyDelete
  31. neat and compact :)))) thanks a lot

    ReplyDelete
  32. Its really usefull.Thank uuuuuuuu
    verymuch.

    BY
    SATISH

    ReplyDelete
  33. really really effective coding

    ReplyDelete
  34. i understand links very easily

    islam

    ReplyDelete
  35. very helpfull in understanding the basics of linked lists......thanks a lot....

    ReplyDelete
  36. excellent..n very helpful..!!

    ReplyDelete
  37. Thank you so much for your great efforts, really find very very helpful.

    ReplyDelete
  38. नितेश कुमार गुप्ताSeptember 20, 2011 at 12:47 PM

    Very easy to understand.. thank U

    ReplyDelete
  39. DARN IT MAN!!! I'M PRETTY SURE YOUR CODE HAS A BUG!!! The addEnd method.

    ReplyDelete
  40. Nope, sorry, I think I was wrong.

    ReplyDelete
  41. very simple and easy to do thank you

    ReplyDelete
  42. very simple and easy to do thank you

    ReplyDelete
  43. this was very useful. thanks a lot.

    ReplyDelete
  44. after going through this i got a clear picture of linked list in my mind. Thank you so much .

    ReplyDelete
  45. dis programm is very easy to understand

    ReplyDelete
  46. this post is so simple and easy to understand. Thanks u made me understand link list with so ease

    ReplyDelete
  47. This examples is really good. we better understand this program logic.

    ReplyDelete
  48. Very simple and easy to understand. Thanks for posting this.

    ReplyDelete
  49. Hey...thanks a lot ,its very good to understand

    ReplyDelete
  50. i am doing an assignment & it is helping me alot. Thank You

    ReplyDelete
  51. its good if u include main prog also

    buts its good also,,<<<<<<< awesome explanation

    ReplyDelete
  52. its good if main prog is also used

    but its good
    and awesome explanation

    ReplyDelete
  53. I feel I have given 95% of the program ... take the pieces and make one single piece haha

    ReplyDelete
  54. Thank you for your efforts.
    Good work.
    Regards,

    ReplyDelete
  55. I'm Nguyen Trong Hoa.Thank you very much!

    ReplyDelete
  56. nice explanation... cleared my doubts wel.. thanks..

    ReplyDelete
  57. excellent i aould understand this easily by seeing pictorial representation thanx a lot

    ReplyDelete
  58. Thanks alooooooooooooooooooooooooooooooooooot

    ReplyDelete
  59. thanx a lot..explaination is very good:)

    ReplyDelete
  60. this was very helpful. Thanks a lot.

    ReplyDelete
  61. really good example. worth reading all the article

    ReplyDelete
  62. Thank you very much...
    code was very easy to understand..

    but

    while deleting a node from list based on data
    it will return the control when it reaches the 1st node (node.data==num) but the list contains the duplication of data,How it is going to delete the next node..

    Plz provide the solution...

    ReplyDelete
  63. nice explanation !! awesome

    ReplyDelete
  64. brilliant explanation with the images!Thank You

    ReplyDelete
  65. This is Hell of an Awesome Job bro, this is gonna help me pass my exams, and Understand Linked Lists as well . Hats Off
    Toha Yaseen

    ReplyDelete
  66. for adding at end
    temp2->next=temp1;
    temp2=temp1;
    this sort of code will work........neway grt jb done bro

    ReplyDelete
  67. Your explaination is very easy to understand .
    Thank you so much.

    ReplyDelete
  68. if (Head == NULL)
    {
    //List is Empty
    Head=temp;
    Head->Next=NULL;
    }
    else
    {
    temp->Next=Head;
    Head=temp;
    }

    actually, you don't need the special case Head==NULL. we can simply make Head point to the new node and set node->next to whatever Head was pointing to, and if it was NULL then we'll just have initialized the new node's Next member which we must do anyway.

    ReplyDelete
  69. tahnk you for the post. great explaination

    ReplyDelete
  70. thanx a ton thank thanku thanku

    ReplyDelete
  71. exelent tutorial i needed a brush up on linklist and that did it for me:-)

    ReplyDelete
  72. Thanks buddy..... Helpful..

    ReplyDelete
  73. i didn't understand the reverse function can you elaborate it??

    ReplyDelete
  74. Thanx.!! Very easy & lucid explanation..!!!!

    ReplyDelete
  75. The diagram solved my problem, I was about to smash the computer up!
    Thank you so much for this love love love

    ReplyDelete
  76. Thank you very much :)

    ReplyDelete
  77. Hey Thanks a lot mate..... This is awesome! You just save so many lives !!!!

    ReplyDelete
  78. Very Nice Explanation ..Thank You !!

    ReplyDelete
  79. daca esti roman te spargi otzara de ras!!!!

    ReplyDelete
  80. you are great buddy !! very helpful and very clear

    ReplyDelete
  81. great! very easy to understand :)

    ReplyDelete
  82. good explanation ... Thanks !!!

    ReplyDelete
  83. Thanks a lot! Really helpful!

    ReplyDelete
  84. i have a doubt , while adding at the beginning of the list...
    i feel it should be like below ... if i am wrong correct me.

    if (Head == NULL)
    {
    //List is Empty
    Head=temp;
    temp->Next=NULL;
    }

    ReplyDelete
  85. @preetham

    Since we have already copied temp into Head variable both temp->next and head->next represents the same.

    ReplyDelete
  86. Very simple and neat illustration. Thank You.

    ReplyDelete
  87. Very clearly explained... thanks for sharing this :)

    ReplyDelete
  88. wow nice job done there .. explained very clearly

    ReplyDelete
  89. great explanation thank you!

    ReplyDelete
  90. Thanks !!!!!!!!!!!!!!

    ReplyDelete
  91. You could have better explained this with a diagram better. Since picture worth more than 1000 words you can draw and publish from a software like creately diagram software.

    ReplyDelete
  92. excellent,
    it would have been better if you provide me the linked list class also

    ReplyDelete

Your comments are moderated