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

## 8.26.2009

### Implementation of Singly Linked List

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
}
else
{
}
}

• 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.

{
// If List is empty we create First Node.
}
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;

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)
{
}
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;

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. very good and simple

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

3. Thanks for posting an example.

4. Helps me really friend

5. very good example to understand the singly link list concept

6. thank u verrrrrrrrrrryy much..... post like these simple programs withcomments....

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

8. it's useful for everyone...very great amazing........

9. thanks a lot posting this example.........

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

11. it really very help 4 my subject thanx

12. easy to understand step wise

13. it helped me a lot...thank u very much

14. it helped me a lot...thank u very much

15. simply easy to understand....ty:)

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

17. really helpful...thank you so much

18. Great!!!

19. 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.

20. Wow! Thanks a lot :-)

21. 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

22. gr8 post mate... really good job!

23. superb!!!!!!!!!!!!
simple and easier to understand

24. 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.

25. simple and easy to understand.......

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

27. This is very simple and interesting and it is awesome......

28. really useful

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

30. nice work thanks

31. nice one dude. simple to understand

32. good job...

33. Really very very informative.. great

-Demom

34. really helpful thanks for the blog

35. Really helpful thanks for the blog

36. neat and compact :)))) thanks a lot

37. Its really usefull.Thank uuuuuuuu
verymuch.

BY
SATISH

38. really really effective coding

39. i understand links very easily

islam

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

41. excellent..n very helpful..!!

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

44. à¤¨िà¤¤ेà¤¶ à¤•ुà¤®ाà¤° à¤—ुà¤ª्à¤¤ाSeptember 21, 2011 at 1:17 AM

Very easy to understand.. thank U

45. neat and nice

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

47. Nope, sorry, I think I was wrong.

48. very simple and easy to do thank you

49. very simple and easy to do thank you

50. this was very useful. thanks a lot.

51. Its Really Useful...

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

53. dis programm is very easy to understand

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

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

56. Very simple and easy to understand. Thanks for posting this.

57. Hey...thanks a lot ,its very good to understand

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

59. its good if u include main prog also

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

60. its good if main prog is also used

but its good
and awesome explanation

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

62. thanks a lot it really helped me:)

63. It's so good

64. superb explaination.....very good

65. superb explaination.....very good

66. Good work :)

67. Thank you for your efforts.
Good work.
Regards,

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

69. nice explanation... cleared my doubts wel.. thanks..

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

71. Thanks alooooooooooooooooooooooooooooooooooot

72. good one ...

73. thanx a lot..explaination is very good:)

74. this was very helpful. Thanks a lot.

75. good work buddy thanks!!

76. awesome.....!!!

77. really good example. worth reading all the article

78. 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...

79. good job buddy god bless u

80. nice explanation !! awesome

81. brilliant explanation with the images!Thank You

82. 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

83. Neat and simple

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

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

86. if (Head == NULL)
{
//List is Empty
}
else
{
}

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.

87. tahnk you for the post. great explaination

88. thanx a ton thank thanku thanku

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

90. Its Easy to undestand.........

91. Thanks buddy..... Helpful..

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

93. Thanx.!! Very easy & lucid explanation..!!!!

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

95. Thank you very much :)

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

97. Very Nice Explanation ..Thank You !!

98. daca esti roman te spargi otzara de ras!!!!

99. you are great buddy !! very helpful and very clear

100. great! very easy to understand :)

101. good explanation ... Thanks !!!

102. Thanks a lot! Really helpful!

103. 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
temp->Next=NULL;
}

104. @preetham

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

105. bookmarked this

106. Very simple and neat illustration. Thank You.

107. Very clearly explained... thanks for sharing this :)

108. wow nice job done there .. explained very clearly

109. great explanation thank you!

110. Thanks !!!!!!!!!!!!!!

111. thank you...........

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