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 |

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 |

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

very good and simple

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

ReplyDeleteThanks for posting an example.

ReplyDeleteHelps me really friend

ReplyDeletevery good example to understand the singly link list concept

ReplyDeletethank u verrrrrrrrrrryy much..... post like these simple programs withcomments....

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

ReplyDeleteit's useful for everyone...very great amazing........

ReplyDeletethanks a lot posting this example.........

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

ReplyDeleteit really very help 4 my subject thanx

ReplyDeleteThank you

ReplyDeleteThank you

ReplyDeleteeasy to understand step wise

ReplyDeleteit helped me a lot...thank u very much

ReplyDeleteit helped me a lot...thank u very much

ReplyDeletesimply easy to understand....ty:)

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

ReplyDeletereally helpful...thank you so much

ReplyDeleteGreat!!!

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

ReplyDeleteWow! Thanks a lot :-)

ReplyDeleteIterators 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

ReplyDeletegr8 post mate... really good job!

ReplyDeletesuperb!!!!!!!!!!!!

ReplyDeletesimple and easier to understand

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.

ReplyDeletesimple and easy to understand.......

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

ReplyDeleteThis is very simple and interesting and it is awesome......

ReplyDeletereally useful

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

ReplyDeletenice work thanks

ReplyDeletenice one dude. simple to understand

ReplyDeletegood job...

ReplyDeleteReally very very informative.. great

ReplyDelete-Demom

really helpful thanks for the blog

ReplyDeleteReally helpful thanks for the blog

ReplyDeleteneat and compact :)))) thanks a lot

ReplyDeleteIts really usefull.Thank uuuuuuuu

ReplyDeleteverymuch.

BY

SATISH

really really effective coding

ReplyDeletei understand links very easily

ReplyDeleteislam

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

ReplyDeleteexcellent..n very helpful..!!

ReplyDeletevery helpful

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

ReplyDeleteVery easy to understand.. thank U

ReplyDeleteneat and nice

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

ReplyDeleteNope, sorry, I think I was wrong.

ReplyDeletevery simple and easy to do thank you

ReplyDeletevery simple and easy to do thank you

ReplyDeletethis was very useful. thanks a lot.

ReplyDeleteIts Really Useful...

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

ReplyDeletedis programm is very easy to understand

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

ReplyDeleteThis examples is really good. we better understand this program logic.

ReplyDeleteVery simple and easy to understand. Thanks for posting this.

ReplyDeleteHey...thanks a lot ,its very good to understand

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

ReplyDeleteits good if u include main prog also

ReplyDeletebuts its good also,,<<<<<<< awesome explanation

its good if main prog is also used

ReplyDeletebut its good

and awesome explanation

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

ReplyDeletethanks a lot it really helped me:)

ReplyDeleteIt's so good

ReplyDeletesuperb explaination.....very good

ReplyDeletesuperb explaination.....very good

ReplyDeleteGood work :)

ReplyDeleteThank you for your efforts.

ReplyDeleteGood work.

Regards,

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

ReplyDeletenice explanation... cleared my doubts wel.. thanks..

ReplyDeleteexcellent i aould understand this easily by seeing pictorial representation thanx a lot

ReplyDeleteThanks alooooooooooooooooooooooooooooooooooot

ReplyDeletegood one ...

ReplyDeletegr8

ReplyDeleteGreat!

ReplyDeletethanx a lot..explaination is very good:)

ReplyDeletethis was very helpful. Thanks a lot.

ReplyDeletegood work buddy thanks!!

ReplyDeleteawesome.....!!!

ReplyDeletereally good example. worth reading all the article

ReplyDeleteThank you very much...

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

good job buddy god bless u

ReplyDeletenice explanation !! awesome

ReplyDeletebrilliant explanation with the images!Thank You

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

ReplyDeleteToha Yaseen

Neat and simple

ReplyDeletefor adding at end

ReplyDeletetemp2->next=temp1;

temp2=temp1;

this sort of code will work........neway grt jb done bro

Your explaination is very easy to understand .

ReplyDeleteThank you so much.

if (Head == NULL)

ReplyDelete{

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

tahnk you for the post. great explaination

ReplyDeletethnx man

ReplyDeletethanx a ton thank thanku thanku

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

ReplyDeleteIts Easy to undestand.........

ReplyDeletesuperb!!

ReplyDeleteThanks buddy..... Helpful..

ReplyDeletei didn't understand the reverse function can you elaborate it??

ReplyDeleteThanx.!! Very easy & lucid explanation..!!!!

ReplyDeleteThe diagram solved my problem, I was about to smash the computer up!

ReplyDeleteThank you so much for this love love love

Thank you very much :)

ReplyDeleteThank you

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

ReplyDeleteVery Nice Explanation ..Thank You !!

ReplyDeletedaca esti roman te spargi otzara de ras!!!!

ReplyDeleteyou are great buddy !! very helpful and very clear

ReplyDeletegreat! very easy to understand :)

ReplyDeletegood explanation ... Thanks !!!

ReplyDeleteThanks a lot! Really helpful!

ReplyDeletei have a doubt , while adding at the beginning of the list...

ReplyDeletei feel it should be like below ... if i am wrong correct me.

if (Head == NULL)

{

//List is Empty

Head=temp;

temp->Next=NULL;

}

@preetham

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

bookmarked this

ReplyDeleteVery simple and neat illustration. Thank You.

ReplyDeleteVery clearly explained... thanks for sharing this :)

ReplyDeletewow nice job done there .. explained very clearly

ReplyDeletegreat explanation thank you!

ReplyDeleteThanks !!!!!!!!!!!!!!

ReplyDelete