Add Last In Linked List
1. You are given a partially written LinkedList class.Input Format
2. You are required to complete the body of addLast function. This function is supposed to add an element to the end of LinkedList. You are required to update head, tail and size as required.
3. Input and Output is managed for you. Just update the code in addLast function.
Input is managed for youOutput Format
Output is managed for youQuestion Video
NoneSample Input
addLast 10Sample Output
addLast 20
addLast 30
addLast 40
addLast 50
quit
10
20
30
40
50
5
50
-
Editorial
The problem deals with adding a node to the end of a linked list. For this problem, we are already given a class with head, tail, and size as data members and we wish to add a node at the end. The other way to see this problem is that we need to add a node after the tail node. Keeping this in mind there can be two cases:
1. When tail != null
This case deals with a non-empty linked list.
Let us assume a Linked List [1 -> 2 -> 3 -> 4]. The given list has head pointing to the node with value 1 and tail pointing at the node with value 4 and the size of the linked list is 4. Now suppose we need to add a node 5 at the end of the linked list. Now as we know that every node stores the address of its next node in a singly linked list so it means that the node with value 1 stores the address of the node with value 2 and so on, which also concludes that the node with value 4 stores null as there is no node ahead of it. Therefore, all we need to do is to update the address of the tail (i.e. the node with value 4) to point to a new node (i.e. the node with value 5) which makes our linked list [1 -> 2 -> 3 -> 4 -> 5]. Now all that is left to do is to update the tail pointer to the node with value 5 and increment the size of the list.
2. When tail == null
This is the case of an empty linked list. This implies that both the head and the tail pointer points to null and the size of our linked list is 0. So here we just need to add our new node to the list which will act as both head and tail (as a list of size 1 has only one node with head and tail both pointing to that node) and we need to increment the size of the list.
Below is the implementation in Java :
void addLast(int val) { Node temp = new Node(); temp.data = val; temp.next = null; if (size == 0) { head = tail = temp; } else { tail.next = temp; tail = temp; } size++; }java false
Time Complexity: O(1)
The time complexity for this function is constant since all we have to do is to update the tail pointer and increment the size of the list which has nothing to do with the number of elements present in the list.
Had it been the case where we have not been provided with the tail pointer then we would have to traverse the entire list to reach the end node of the list which would take a time complexity proportional to the length of the list and then we would insert a node and increment the size, so the total time complexity would have been O(n) in that case, where n is the length of the linked list.
Space Complexity: O(1)
As we only take a space to create a new node which is also independent of the length of the linked list.
-
Asked in Companies
-
Related Topics
