Determining the Complexity of appending a value at the end of a List

Question

As we know, to push an element at the front of list requires O(1) time. Now consider we want to put (or append) an element at the end of list. What is the complexity of this operation?

Now consider, to put an element at the end of list, we need to traverse the list up to the end (because of not having prev. pointer), requires O(n) time complexity. Will it possible to make this in O(1)?

I did some implementation, while appending value at the end, I am keeping the next place in pointer, where node can be inserted. Check out the following please:

import java.util.*; class List{ int data; List next; List(int data){ this.data = data; } } class Driver{ List head, temp; Driver(){ head = null; temp = head; } void push(int item){ if(head == null){ head = new List(item); temp = head; } else { temp.next = new List(item); temp = temp.next; } } } class AppendInList{ public static void main(String [] args){ Driver obj = new Driver(); obj.push(5); obj.push(66); } }

I searched in SO, but I didn't get anything for my satisfaction! Correct me if I did some mistake!

"As we know, to push an element at the front of list requires O(1) time" -> Wrong. Let the teacher who gave this assignment know this. — iavanish
– iavanish, Commented Feb 26, 2019 at 8:41

uneq95 · Accepted Answer · 2019-02-26 09:01:07Z

You can push an element to the front of a linked list in O(1) time, if you save a reference to the front/head element in the linked list data structure.

Similarly, you could maintain a reference to the last element, using which you could add an element to the last in O(1) time. You would have to update the last pointer every time you add an element.

The data structure could look like below:

class List{ ListNode head;//ListNode class stores next reference and value of the node ListNode tail;//last element void pushToLast(ListNode newElement){ //TODO : Take care of corner cases tail.next = newElement; tail = newElement; } }

Collectives™ on Stack Overflow

Determining the Complexity of appending a value at the end of a List

1 Answer 1

Comments

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Related