Add First In Linked List
1. You are given a partially written LinkedList class.Input Format
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 is managed for youOutput Format
Output is managed for youQuestion Video
NoneSample Input
addFirst 10Sample Output
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
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
