How can adding at end of linklist be o(1)

#1

I think we will need to traverse first and then add to list it will be o(n)

#2

@pallavigoel1996,
Adding at the end of a Linked List can be optimized to work in O(1) by keeping an extra pointer to tail of linked list.

#3

Are you making it a double linklist???

#4

As for that too yoi need to traverse the linklist and that takes 0(n) for placing the pointer tail at last.

#5

@pallavigoel1996,
No, we will store the tail node of the linked list and update it after every element we append.
Example:
We have to create a linked list of 3 elements.
We add the first element, the LL is: 1 and in the tail node we store 1.
Now we have to add the second element, 2. Now in this case, tail.next = Node(2) and tail = Node(2). LL is 1->2 and tail node is 2.

The tail node is null when the list is empty, otherwise it always points to the last node.
This is the code we can use:

public void append(int data){
//if head is null{
 
 }
Node nn = new Node(data);
tail.next = nn;
tail = nn;

}

1 Like
#6

Okay understood.Thanks :slight_smile:

#7

@pallavigoel1996,
Kindly mark the doubt as resolved and drop a like/rating too. Thanks. And if you any other query please let me know.

#8

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.

1 Like