Add Last In Linked List

Try First, Check Solution later

1. You should first read the question and watch the question video.
2. Think of a solution approach, then try and submit the question on editor tab.
3. We strongly advise you to watch the solution video for prescribed approach.

1. You are given a partially written LinkedList class.
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 Format
Input is managed for you
Output Format
Output is managed for you
Question Video
Constraints
None
Sample Input
addLast 10
addLast 20
addLast 30
addLast 40
addLast 50
quit
Sample Output
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






Video Solution

Code Solution

Run
 
Run
Id Name