Add First 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. Here is a list of existing functions:
2.1 addLast - adds a new element with given value to the end of Linked List
2.2. display - Prints the elements of linked list from front to end in a single line.
All elements are separated by space.
2.3. size - Returns the number of elements in the linked list.
2.4. removeFirst - Removes the first element from Linked List.
2.5. getFirst - Returns the data of first element.
2.6. getLast - Returns the data of last element.
2.7. getAt - Returns the data of element available at the index passed.
3. You are required to complete the body of addFirst function. This function should add the element to the beginning of the linkedlist and appropriately set the head, tail and size data-members.
4. Input and Output is managed for you.
Input Format
Input is managed for you
Output Format
Output is managed for you
Question Video
Constraints
None
Sample Input
addFirst 10
getFirst
addFirst 20
getFirst
getLast
display
size
addLast 40
getLast
addLast 50
addFirst 30
removeFirst
getFirst
removeFirst
removeFirst
getAt 3
display
size
removeFirst
removeFirst
getFirst
quit
Sample Output
10
20
10
20 10
2
40
20
Invalid arguments
40 50
2
List is empty


  • Editorial

    The problem deals with adding a node at the beginning of the linked list.Say for example we have a list, 1 -> 2 -> 3 -> 4 -> 5 and we wish to add node with value 10 at the beginning so our list should look like, 10 ->1 -> 2 -> 3 -> 4 -> 5

    Also, we are given a linked list class which has three data members:

    1. Head: It points to the starting node of the linked list.

    2. Tail: It points to the last node of the linked list.

    3. Size: It stores the current length (or size) of the linked list.

    The problem can be categorized into two different cases:

    1. Size != 0

    This is the case when our list is not empty. So we need to create a new node and store the input data, now the next thing to keep in mind is that this new node will now act as the head of the linked list so the head should be updated, also the new node should now point to the next node which was the previous head and lastly, the size of the list should be incremented.

    2. Size == 0

    This is the case when our list is empty. For that adding a new node to the list will make the length of the list as 1. Now as we already know that for an empty list head = tail = null and size = 0, so after adding the new node both head and tail should point to our new node and size should also be incremented.

    Below is the implementation in Java:

    public void addFirst(int val) {
                                        Node temp = new Node();
                                        temp.data = val;
                                        temp.next = head;
                                        head = temp; 
                                        if (size == 0) {
                                        tail = temp;
                                        } 
                                        size++;
                                    }

    java false

    Time Complexity: O(1)

    The time complexity for the function is constant as the only operation include here is updation of data members.

    Space Complexity: O(1)

    The space complexity for the function is constant as we have only created a new node variable that takes constant space.

  • Asked in Companies
  • Related Topics






Video Solution

Code Solution

Run
 
Run
Id Name