Linked List – Insertion at Tail | C, Java, and Python Implementation
In the previous two posts (here and here), we have introduced linked list data structure and discussed various types of linked lists. We also covered in great detail the various methods to construct a linked list that inserts every new node onto the list’s front. This post will discuss various methods to implement a linked list by inserting it at the tail of the singly linked list.
A simple solution would be to locate the last node in the list and then change its .next field from NULL to point the new node. This is just a particular case of the general rule: to insert or delete a node inside a list, we need a pointer to the node just before that position to change its .next field. Many list problems include the subproblem of advancing a pointer to the node before the point of insertion or deletion. The one exception is if the node is first in the list – in that case, we must change the head pointer.
Consider below the appendNode() function, which is like push(), except it adds the new node at the tail end of the list instead of the head. If the list is empty, it uses the reference pointer to change the head pointer. Otherwise, it uses a loop to locate the last node in the list. This version does not use push(), but builds the new node directly.
Following is the C, Java, and Python program that demonstrates it:
C
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 |
#include <stdio.h> #include <stdlib.h> // A Linked List Node struct Node { int data; struct Node* next; }; // Helper function to return new linked list node from the heap struct Node* newNode(int key) { struct Node* node = (struct Node*)malloc(sizeof(struct Node)); node->data = key; node->next = NULL; return node; } // Helper function to print a given linked list void printList(struct Node* head) { struct Node* ptr = head; while (ptr) { printf("%d —> ", ptr->data); ptr = ptr->next; } printf("NULL"); } // Function to add a new node at the tail end of the list instead of its head struct Node* appendNode(struct Node** head, int key) { struct Node* current = *head; struct Node* node = newNode(key); // special case for length 0 if (current == NULL) { *head = node; } else { // locate the last node while (current->next != NULL) { current = current->next; } current->next = node; } } int main(void) { // input keys int keys[] = {1, 2, 3, 4}; int n = sizeof(keys)/sizeof(keys[0]); // points to the head node of the linked list struct Node* head = NULL; for (int i = 0; i < n; i++) { appendNode(&head, keys[i]); } // print linked list printList(head); return 0; } |
Output:
1 —> 2 —> 3 —> 4 —> NULL
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 |
// A Linked List Node class Node { int data; Node next; Node(int data, Node next) { this.data = data; this.next = next; } } class Main { // Helper function to return new linked list node from the heap public static Node newNode(int key) { Node node = new Node(key, null); return node; } // Helper function to print a given linked list public static void printList(Node head) { Node ptr = head; while (ptr != null) { System.out.print(ptr.data + " —> "); ptr = ptr.next; } System.out.println("null"); } // Function to add a new node at the tail end of the list instead of its head public static Node appendNode(Node head, int key) { Node current = head; Node node = newNode(key); // special case for length 0 if (current == null) { head = node; } else { // locate the last node while (current.next != null) { current = current.next; } current.next = node; } return head; } public static void main(String[] args) { // input keys int[] keys = {1, 2, 3, 4}; // points to the head node of the linked list Node head = null; for (int key: keys) { head = appendNode(head, key); } // print linked list printList(head); } } |
Output:
1 —> 2 —> 3 —> 4 —> null
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 |
# A Linked List Node class Node: def __init__(self, data=None, next=None): self.data = data self.next = next # Helper function to print a given linked list def printList(head): ptr = head while ptr: print(ptr.data, end=' —> ') ptr = ptr.next print('None') # Function to add a node at the tail end of the list instead of its head def appendNode(head, key): current = head node = Node(key) # special case for length 0 if current is None: head = node else: # locate the last node while current.next: current = current.next current.next = node return head if __name__ == '__main__': # input keys keys = [1, 2, 3, 4] # points to the head node of the linked list head = None for key in keys: head = appendNode(head, key) # print linked list printList(head) |
Output:
1 —> 2 —> 3 —> 4 —> None
The following version is very similar to the above code but relies on push() to build the new node. Understanding this version requires a real understanding of reference pointers.
C
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 |
#include <stdio.h> #include <stdlib.h> // A Linked List Node struct Node { int data; struct Node* next; }; // Helper function to print a given linked list void printList(struct Node* head) { struct Node* ptr = head; while (ptr) { printf("%d —> ", ptr->data); ptr = ptr->next; } printf("NULL"); } // Helper function to insert a new node at the beginning of the linked list void push(struct Node** head, int data) { // allocate a new node in a heap and set its data struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); newNode->data = data; // set the `.next` pointer of the new node to point to the current // first node of the list. newNode->next = *head; // change the head pointer to point to the new node, so it is // now the first node in the list. *head = newNode; } // Function to add a new node at the tail end of the list instead // of its head struct Node* appendNode(struct Node** head, int key) { struct Node* current = *head; // special case for the empty list if (current == NULL) { push(head, key); } else { // locate the last node while (current->next != NULL) { current = current->next; } // Build the node after the last node push(&(current->next), key); } } int main(void) { // input keys int keys[] = {1, 2, 3, 4}; int n = sizeof(keys)/sizeof(keys[0]); // points to the head node of the linked list struct Node* head = NULL; for (int i = 0; i < n; i++) { appendNode(&head, keys[i]); } // print linked list printList(head); return 0; } |
Output:
1 —> 2 —> 3 —> 4 —> NULL
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 |
// A Linked List Node class Node { int data; Node next; } class Main { // Helper function to print a given linked list public static void printList(Node head) { for (Node ptr = head; ptr != null; ptr = ptr.next) { System.out.print(ptr.data + " —> "); } System.out.println("null"); } // Helper function to insert a new node at the beginning of the linked list public static Node push(int data, Node head) { // allocate a new node in a heap and set its data Node newNode = new Node(); newNode.data = data; // set the next field of the new node to point to the current // first node of the list. newNode.next = head; // return the head to point to the new node, so it is // now the first node in the list. return newNode; } // Function to add a new node at the tail end of the list instead // of its head public static Node appendNode(Node head, int key) { Node current = head; // special case for the empty list if (head == null) { head = push(key, null); } else { // locate the last node while (current.next != null) { current = current.next; } // Build the node after the last node current.next = push(key, null); } return head; } public static void main(String[] args) { // input keys int[] keys = {1, 2, 3, 4}; // points to the head node of the linked list Node head = null; for (int key: keys) { head = appendNode(head, key); } // print linked list printList(head); } } |
Output:
1 —> 2 —> 3 —> 4 —> null
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 |
# A Linked List Node class Node: next = None # Constructor def __init__(self, data): self.data = data # Function to print a given linked list def printList(head): ptr = head while ptr: print(ptr.data, end=' —> ') ptr = ptr.next print('None') # Function to insert a node at the beginning of the linked list def push(head, data): # allocate a new node in a heap and set its data newNode = Node(data) # set the next field of the node to point to the current # first node of the list. newNode.next = head # return the head to point to the node, so it is # now the first node in the list. return newNode # Function to add a node at the tail end of the list instead # of its head def appendNode(head, key): current = head # special case for the empty list if current is None: head = push(head, key) else: # locate the last node while current.next: current = current.next # Build the node after the last node current.next = push(current.next, key) return head if __name__ == '__main__': # input keys keys = [1, 2, 3, 4] # points to the head node of the linked list head = None for key in keys: head = appendNode(head, key) # print linked list printList(head) |
Output:
1 —> 2 —> 3 —> 4 —> None
The time complexity in the above solution would be linear for each insertion as we are traversing the whole list till the very end. An efficient approach is maintaining a tail pointer and a head pointer to perform insertion in constant time. There are two standard ways to do it:
1. Build using Dummy Node
The idea is to use a temporary dummy node at the head of the list during computation. The trick is that every node appears to be added after the .next field of a node with the dummy. That way, the code for the first node is the same as for the other nodes. The tail pointer plays the same role as in the previous example. It now also handles the first node (avoids making dummy a permanent part of the list).
Following is the C, Java, and Python program that demonstrates it:
C
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 |
#include <stdio.h> #include <stdlib.h> // A Linked List Node struct Node { int data; struct Node* next; }; // Helper function to print a given linked list void printList(struct Node* head) { struct Node* ptr = head; while (ptr) { printf("%d —> ", ptr->data); ptr = ptr->next; } printf("NULL"); } /* Takes a list and a data value, creates a new link with the given data and pushes it onto the list's front. The head node is passed by reference. */ void push(struct Node** head, int data) { // allocate a new node in a heap and set its data struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); newNode->data = data; // set the `.next` pointer of the new node to point to the current // first node of the list. newNode->next = *head; // change the head pointer to point to the new node, so it is // now the first node in the list. *head = newNode; } // Function to implement a linked list from a given set of keys // using a dummy node struct Node* constructList(int keys[], int n) { struct Node dummy; // dummy node is temporarily the first node struct Node* tail = &dummy; // start the tail at the dummy // Build the list on `dummy->next` (aka `tail->next`) dummy.next = NULL; for (int i = 0; i < n; i++) { push(&(tail->next), keys[i]); tail = tail->next; } // The real result list is now in `dummy.next` // dummy.next == {key[0], key[1], key[2], key[3]}; return (dummy.next); } int main() { // input keys int keys[] = { 1, 2, 3, 4 }; int n = sizeof(keys) / sizeof(keys[0]); // points to the head node of the linked list struct Node* head = constructList(keys, n); // print linked list printList(head); return 0; } |
Output:
1 —> 2 —> 3 —> 4 —> NULL
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 |
// A Linked List Node class Node { int data; Node next; } class Main { // Helper function to print a given linked list public static void printList(Node head) { Node ptr = head; while (ptr != null) { System.out.print(ptr.data + " —> "); ptr = ptr.next; } System.out.println("null"); } /* Takes a list and a data value, creates a new link with the given data and pushes it onto the list's front. */ public static Node push(Node head, int data) { // allocate a new node in a heap and set its data Node newNode = new Node(); newNode.data = data; // set the next field of the new node to point to the current // first node of the list. newNode.next = head; // change the head to point to the new node, so it is // now the first node in the list. return newNode; } // Function to implement a linked list from a given set of keys // using a dummy node public static Node constructList(int[] keys) { Node dummy = new Node(); // dummy node is temporarily the first node Node tail = dummy; // start the tail at the dummy // Build the list on `dummy.next` (aka `tail.next`) for (int key: keys) { tail.next = push(tail.next, key); tail = tail.next; } // The real result list is now in `dummy.next` // dummy.next == {key[0], key[1], key[2], key[3]}; return (dummy.next); } public static void main(String[] args) { // input keys int[] keys = {1, 2, 3, 4}; // points to the head node of the linked list Node head = constructList(keys); // print linked list printList(head); } } |
Output:
1 —> 2 —> 3 —> 4 —> None
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 |
# A Linked List Node class Node: # Constructor def __init__(self, data=None, next=None): self.data = data self.next = next # Function to print a given linked list def printList(head): ptr = head while ptr: print(ptr.data, end=' —> ') ptr = ptr.next print('None') # Takes a list and a data value, creates a new link with the given data # and pushes it onto the list's front. def push(head, data): # allocate a new node in a heap and set its data newNode = Node(data) # set the next field of the node to point to the current # first node of the list. newNode.next = head # change the head to point to the new node, so it is # now the first node in the list. return newNode # Function to implement a linked list from a given set of keys # using a dummy node def constructList(keys): dummy = Node() # dummy node is temporarily the first node tail = dummy # start the tail at the dummy # Build the list on `dummy.next` (aka `tail.next`) for key in keys: tail.next = push(tail.next, key) tail = tail.next # The real result list is now in `dummy.next` # dummy.next == key[0], key[1], key[2], key[3] return dummy.next if __name__ == '__main__': # input keys keys = [1, 2, 3, 4] # points to the head node of the linked list head = constructList(keys) # print linked list printList(head) |
Output:
1 —> 2 —> 3 —> 4 —> None
Some linked list implementations keep the dummy node as a permanent part of the list. For this “permanent dummy” strategy, the empty list is not represented by a NULL pointer. Instead, every list has a dummy node at its head. The algorithms skip over the dummy node for all operations. The heap-allocated dummy node is always present to provide the above sort of convenience in the code.
2. Build using Local References
A tricky way to unifying all the node cases without using a dummy node is to use a local “reference pointer”, which always points to the last pointer in the list instead of the last node. All additions to the list are made by following the reference pointer. The reference pointer starts by pointing to the head pointer. Later, it points to the .next field inside the last node in the list.
The implementation can be seen below in C:
C
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 |
#include <stdio.h> #include <stdlib.h> // A Linked List Node struct Node { int data; struct Node* next; }; // Helper function to print a given linked list void printList(struct Node* head) { struct Node* ptr = head; while (ptr) { printf("%d —> ", ptr->data); ptr = ptr->next; } printf("NULL"); } /* Takes a list and a data value, creates a new link with the given data and pushes it onto the list's front. The head node is passed by reference. */ void push(struct Node** head, int data) { // allocate a new node in a heap and set its data struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); newNode->data = data; // set the `.next` pointer of the new node to point to the current // first node of the list. newNode->next = *head; // change the head pointer to point to the new node, so it is // now the first node in the list. *head = newNode; } // Function to implement a linked list from a given set of keys // using local references struct Node* constructList(int keys[], int n) { struct Node* head = NULL; // `lastPtrRef` points to the last pointer (`.next` field inside the last node) // in the list. Initially, it points to the head pointer itself struct Node** lastPtrRef = &head; for (int i = 0; i < n; i++) { // adds a new node at the last pointer. The new node becomes the // last node in the list push(lastPtrRef, keys[i]); // advance `lastPtrRef` to now point to the `.next` field inside lastPtrRef= &((*lastPtrRef)->next); } // head == {key[0], key[1], key[2], key[3]}; return head; } int main() { // input keys int keys[] = { 1, 2, 3, 4 }; int n = sizeof(keys) / sizeof(keys[0]); // points to the head node of the linked list struct Node* head = constructList(keys, n); // print linked list printList(head); return 0; } |
Source: http://cslibrary.stanford.edu/103/LinkedListBasics.pdf
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)