Singly Linked Lists (With Code in C, C++, Java, and Python)
Introduction
Singly linked lists are a type of a linked list where each node points to the next node in the sequence. It does not have any pointer that points to the previous node. That means we can traverse the list only in forward direction. Figure 1 shows an example of a singly linked list with 4 nodes.
The first item in the list is pointed by a pointer called head. Sometimes we use another pointer called tail that points to the last item in the list. I am using only head in this tutorial to make it simple.
Operations on a singly linked list
Insert item at the head
Inserting an item at the head of the list requires 3 steps.
Create a new node. Insert the item in the data field of the node.
Set the new node’s next pointer to the node current head is pointing to.
Make the head pointer point to the newly added node.
Insert an item at the end
To insert an item at the end of the list, use following steps.
Seek through the list until the final node is reached.
Create a new node using the item to be inserted.
Set the last node’s next pointer to the newly created node.
Set the next pointer of the new node to null.
Insert item after another item
To insert an item anywhere between the first and the last node, use the following steps.
Seek through the list until the desired node N (after which you want to insert the new node) is found.
Create a new node using the item to be inserted.
Set the new node’s next pointer to the node N.
Set N’s next pointer to the newly created node.
Searching an item in the list
Searching for an item in the list requires the following step.
Start with the head.
If the data matches, your search is complete.
If the data does not match, go to the next node and repeat step 2.
If the next of the item is null, we reach the end of the list and data is not found in the list.
Delete item at the head
For all the delete operations, please keep in mind that, the object needs to be deleted from the heap memory. Languages like Java, Python have Garbage Collector that takes care of this but in C/C++ you need to delete the objects yourself
Use the following steps to delete the item at the head of the linked list.
Set the next pointer of the first node to null.
Move the current head of the list to the second node.
Delete the first node.
Delete item at the end
Use the following steps to delete the item at the end of the list.
Seek through the list until you get to the last node (You might need to keep track of the previous node as well).
Set the previous node’s next to null.
Delete the last node.
Delete item anywhere in the list
Search the list until you find the item you are looking for (You might need to keep track of the previous node as well). Let’s call this node N.
Set N’s previous node’s next to the N’s next node’s next.
Delete N.
Complexities
The complexities of the operations discussed above are summarized in the table below.
Operation
Complexity
Insert at the head
O(1)
Insert at the end
O(n)
Insert at the middle
O(n)
Delete at the head
O(1)
Delete at the end
O(n)
Delete at the middle
O(n)
Search the list
O(n)
The complexities given above are for the linked list that has only head pointer. If we have tail pointer then inserting at the end takes only a constant time.
// C implementation of singly linked list #include #include
// data structure for Node // data -> the actual value // next -> address of the next node structNode { int data; structNode *next; };
typedefstructNode *NodePtr;
// global variable head. It points to the // first node of the list NodePtr head = NULL;
// check if the list is empty intisEmpty(){ return head == NULL; }
// Insert 'value' at the front of the list voidinsertAtFront(int value){ NodePtr node = malloc(sizeof(NodePtr)); node->data = value; node->next = NULL; if (isEmpty()) { head = node; } else { node->next = head; head = node; }
} // insert value at the back of the linked list voidinsertAtBack(int value){ NodePtr node = malloc(sizeof(NodePtr)); node->data = value; node->next = NULL; if (isEmpty()) { head = node; } else { // find the last node NodePtr currPtr = head; while (currPtr->next != NULL) { currPtr = currPtr->next; } // insert it currPtr->next = node; } } // inserts value after key NodePtr insertAfter(int key, int value){ NodePtr node = malloc(sizeof(NodePtr)); node->data = value; node->next = NULL;
// find the position of key NodePtr currPtr = head; while (currPtr != NULL && currPtr->data != key) { currPtr = currPtr->next; } // if key is not there, raise error if (currPtr == NULL) { printf("%s", "key not found"); } elseif (currPtr->next == NULL) { // if key is the last node, insert right after it currPtr->next = node; } else { // insert between key and item next to key NodePtr nextPtr = currPtr->next; currPtr->next = node; node->next = nextPtr; } } // returns the data at first node inttopFront(){ if (isEmpty()) { printf("%s", "List is empty"); } else { return head->data; } }
// returns the data at last node inttopBack(){ if (isEmpty()) { printf("%s", "List is empty"); } elseif (head->next == NULL) { return head->data; } else { NodePtr currPtr = head; while (currPtr->next != NULL) { currPtr = currPtr->next; } return currPtr->data; } }
// removes the item at front of the linked list and return intpopFront(){ int item; if (isEmpty()) { printf("%s", "List is empty"); return-99999; } else { NodePtr nextPtr = head->next; item = head->data; // remove head free(head); // make nextptr head head = nextPtr; } return item; }
// remove the item at the list of the linked list and return intpopBack(){ int item; if (isEmpty()) { printf("%s", "List is empty"); return-99999; } elseif (head->next == NULL) { item = head->data; free(head); head = NULL; } else { NodePtr currPtr = head; NodePtr prevPtr = NULL; while (currPtr->next != NULL) { prevPtr = currPtr; currPtr = currPtr->next; } item = currPtr->data; free(currPtr); currPtr = NULL; prevPtr->next = NULL; } return item; }
// removes an item with value 'key' voiddelete(int key){ if (isEmpty()) { printf("%s", "List is empty"); return; } // get to the position of key NodePtr prevPtr = NULL; NodePtr currPtr = head; while(currPtr != NULL && currPtr->data != key) { prevPtr = currPtr; currPtr = currPtr->next; } if (currPtr == NULL) { printf("%s", "Key is not found in the list"); return; } if (prevPtr == NULL) { // this is the first item head = head->next; free(currPtr); currPtr = NULL; return; } if (currPtr->next == NULL) { // this is the last item prevPtr->next = NULL; free(currPtr); currPtr = NULL; } else { // anywhere in between first and last NodePtr nextPtr = currPtr->next; prevPtr->next = nextPtr; free(currPtr); currPtr = NULL; } }
// print the linked list voidprint(){ NodePtr currPtr = head; while (currPtr != NULL) { printf("%d", currPtr->data); printf(" "); currPtr = currPtr->next; } printf("\n"); }
// check if a key is in the list intfind(int key){ if (isEmpty()) { return0; }
// C++ implementation of singly linked list #include
usingnamespacestd;
// data structure for Node // data -> the actual value // next -> address of the next node structNode { int data; Node *next; };
typedef Node *NodePtr;
classMyLinkedList { private: NodePtr head;
public: MyLinkedList() { head = nullptr; } // Insert 'value' at the front of the list voidinsertAtFront(int value){ NodePtr node = new Node; node->data = value; node->next = nullptr; if (isEmpty()) { head = node; } else { node->next = head; head = node; } } // insert value at the back of the linked list voidinsertAtBack(int value){ NodePtr node = new Node; node->data = value; node->next = nullptr; if (isEmpty()) { head = node; } else { // find the last node NodePtr currPtr = head; while (currPtr->next != nullptr) { currPtr = currPtr->next; } // insert it currPtr->next = node; } } // inserts value after key voidinsertAfter(int key, int value){ NodePtr node = new Node; node->data = value; node->next = nullptr;
// find the position of key NodePtr currPtr = head; while (currPtr != nullptr && currPtr->data != key) { currPtr = currPtr->next; } // if key is not there, raise error if (currPtr == nullptr) { cout<<"key not found"; } elseif (currPtr->next == nullptr) { // if key is the last node, insert right after it currPtr->next = node; } else { // insert between key and item next to key NodePtr nextPtr = currPtr->next; currPtr->next = node; node->next = nextPtr; } } // returns the data at first node inttopFront(){ if (isEmpty()) { cout<<"List is empty"<<endl; } else { return head->data; } } // returns the data at last node inttopBack(){ if (isEmpty()) { cout<<"List is empty"<<endl; } elseif (head->next == nullptr) { return head->data; } else { NodePtr currPtr = head; while (currPtr->next != nullptr) { currPtr = currPtr->next; } return currPtr->data; } } // removes the item at front of the linked list and return intpopFront(){ int item; if (isEmpty()) { cout<<"List is empty"<<endl; return-99999; } else { NodePtr nextPtr = head->next; item = head->data; // remove head delete head; // make nextptr head head = nextPtr; } return item; } // remove the item at the list of the linked list and return intpopBack(){ int item; if (isEmpty()) { cout<<"List if empty"<<endl; return-99999; } elseif (head->next == nullptr) { item = head->data; delete head; head = nullptr; } else { NodePtr currPtr = head; NodePtr prevPtr = nullptr; while (currPtr->next != nullptr) { prevPtr = currPtr; currPtr = currPtr->next; } item = currPtr->data; delete currPtr; currPtr = nullptr; prevPtr->next = nullptr; } return item; } // removes an item with value 'key' voidremove(int key){ if (isEmpty()) { cout<<"list is empty"<<endl; return; } // get to the position of key NodePtr prevPtr = nullptr; NodePtr currPtr = head; while(currPtr != nullptr && currPtr->data != key) { prevPtr = currPtr; currPtr = currPtr->next; } if (currPtr == nullptr) { cout<<"Key is not found in the list"<<endl; return; } if (prevPtr == nullptr) { // this is the first item head = head->next; delete currPtr; currPtr = nullptr; return; } if (currPtr->next == nullptr) { // this is the last item prevPtr->next = nullptr; delete currPtr; currPtr = nullptr; } else { // anywhere in between first and last NodePtr nextPtr = currPtr->next; prevPtr->next = nextPtr; delete currPtr; currPtr = nullptr; } } // print the linked list voidprint(){ NodePtr currPtr = head; while (currPtr != nullptr) { cout<data<<" "; currPtr = currPtr->next; } cout<<endl; }
// check if the list is empty boolisEmpty(){ return head == nullptr; }
// check if a key is in the list boolfind(int key){ if (isEmpty()) { returnfalse; }
// Insert 'value' at the front of the list publicvoidinsertAtFront(int value){ Node node = new Node(value); if(isEmpty()) { head = node; } else { node.next = head; head = node; } }
// insert value at the back of the linked list publicvoidinsertAtBack(int value){ Node node = new Node(value); if (isEmpty()) { head = node; } else { Node curr = head; while(null != curr.next) { curr = curr.next; }
curr.next = node; } }
// inserts value after key publicvoidinsertAfter(int key, int value){ Node node = new Node(value);
// find the position of key Node curr = head; while(null != curr && curr.data != key) { curr = curr.next; }
if (null == curr) { System.out.println("Key not found"); return; }
// removes the item at front of the linked list and return publicintpopFront(){ if (isEmpty()) { System.out.println("List is empty"); return -999999; }
Node next = head.next; int item = head.data; head = next; return item; }
// remove the item at the end of the list and return publicintpopBack(){ if (isEmpty()) { System.out.println("List is empty"); return -999999; }
// get to the last node Node curr = head; Node prev = null; while(curr.next != null) { prev = curr; curr = curr.next; }
int item = curr.data;
if (prev == null) { // the list has only one item head = null; } else { prev.next = null; curr = null; }
return item; }
// removes an item with value 'key' publicvoidremove(int key){ if (isEmpty()) { System.out.println("List is empty"); return; }
// find the position of the key Node curr = head; Node prev = null;
if(curr == null) { System.out.print("key not found"); return; }
// if curr is head, delete the head if (prev == null) { head = head.next; curr = null; } elseif (curr.next == null) { // if curr is last item prev.next = null; curr = null; } else { //anywhere between first and last node Node next = curr.next; prev.next = next; curr = null; }
}
// check if the key is in the list publicbooleanfind(int key){ if (isEmpty()) { System.out.println("List is empty"); returnfalse; }
# Insert 'value' at the front of the list definsert_at_front(self, value): node = Node(value) if self.is_empty(): self.head = node else: node.next = self.head self.head = node # insert value at the back of the linked list definsert_at_back(self, value): node = Node(value) if self.is_empty(): self.head = node else: curr = self.head while curr.next != None: curr = curr.next curr.next = node
# inserts value after key definsert_after(self, key, value): node = Node(value)
# find the position of key curr = self.head while curr != Noneand curr.data != key: curr = curr.next
# if curr is head, delete the head if prev == None: self.head = self.head.next curr = None elif curr.next == None: # if curr is last item prev.next = None curr = None else: #anywhere between first and last node next_node = curr.next prev.next = next_node curr = None
# check if the key is in the list deffind(self, key): if self.is_empty(): print'List is empty' returnFalse