Question

Can a linked list ever have an O(n^2) behavior? For remove, add, and search as well?

Can an array list have an O(n^2) behavior as well?

Answer 1

Both Arrays and Linked List can be used to store linear data of similar types, but they both have some advantages and disadvantages over each other.

LinkedList:-

Following are the points in favour of Linked Lists:.

1. The size of the arrays is fixed: So we must know the upper limit on the number of elements in advance. Also, generally, the allocated memory is equal to the upper limit irrespective of the usage, and in practical uses, upper limit is rarely reached.
2. Inserting a new element in an array of elements is expensive, because room has to be created for the new elements and to create room existing elements have to shifted.

For example:, suppose we maintain a sorted list of IDs in an array id[].

id[] = [1000, 1010, 1050, 2000, 2040, …..].

And if we want to insert a new ID 1005, then to maintain the sorted order, we have to move all the elements after 1000 (excluding 1000).

Deletion is also expensive with arrays until unless some special techniques are used. For example, to delete 1010 in id[], everything after 1010 has to be moved.

So Linked list provides following two advantages over arrays:

1. Dynamic size
2. Ease of insertion/deletion

Linked lists have following drawbacks:

1. Random access is not allowed. We have to access elements sequentially starting from the first node. So we cannot do binary search with linked lists
2. Extra memory space for a pointer is required with each element of the list.
3. Arrays have better cache locality that can make a pretty big difference in performance.

Coming to Add a node in linkedlist:

methods to insert a new node in linked list are discussed. A node can be added in three ways

1. At the front of the linked list
2. After a given node.
3. At the end of the linked list.

At the front of the linkedlist:-

The new node is always added before the head of the given Linked List. And newly added node becomes the new head of the Linked List. For example if the given Linked List is 10->15->20->25 and we add an item 5 at the front, then the Linked List becomes 5->10->15->20->25. Let us call the function that adds at the front of the list is push(). The push() must receive a pointer to the head pointer, because push must change the head pointer to point to the new node.

Time complexity is O(1).

At a given Node:-

We are given pointer to a node, and the new node is inserted after the given node.

Time complexity is O(1) .

At the End of the linked list:

The new node is always added after the last node of the given Linked List. For example if the given Linked List is 5->10->15->20->25 and we add an item 30 at the end, then the Linked List becomes 5->10->15->20->25->30.
Since a Linked List is typically represented by the head of it, we have to traverse the list till end and then change the next of last node to new node.

Time complexity of append is O(n) where n is the number of nodes in linked list. Since there is a loop from head to end, the function does O(n) work.

So,Time complexity is O(n),n-No.of nodes in a linkedlist.

Remove Node from linkedlist:

It can also done in three ways as adding node in the linked list.

1. At Front of the linkedlist    Time complexity -->O(1)
2. At given node                   Time Complexity -->O(givne node)--given node-->position
3. At the end                       Time Complexity -->O(n) where n is no of nodes in a linkedlist

Searching:-

Here,we can search through the all linked list,And If find return True else False

For example, if the key to be searched is 15 and linked list is 14->21->11->30->10, then function should return false. If key to be searched is 14, then the function should return true.

So A linked list can typically only be accessed via its head node. From there you can only traverse from node to node until you reach the node you seek. Thus access is O(n).

Searching for a given value in a linked list similarly requires traversing all the elements until you find that value. Thus search is O(n).

Coming to arrays:

An array is a collection of items stored at contiguous memory locations. The idea is to store multiple items of the same type together. This makes it easier to calculate the position of each element by simply adding an offset to a base value, i.e., the memory location of the first element of the array (generally denoted by the name of the array).

Here, Array size is fixed before taking inputs into the array.And So we must know the upper limit on the number of elements in advance. Also, generally, the allocated memory is equal to the upper limit irrespective of the usage, and in practical uses, upper limit is rarely reached.

Inserting a new element in an array of elements is expensive, because room has to be created for the new elements and to create room existing elements have to shifted.

Add Element into the array    ----->Time Complexity O(1) Just add element into the array.

Delete Element in the array   ----->Time Complexity O(N) where N is Array size.

Search Element in the array ----->Time Complexity O(N) where N is Array size.

Comparision between ArrayList and LinkedList:-

1. Insertions are easy and fast in LinkedList as compared to ArrayList because there is no risk of resizing array and copying content to new array if array gets full which makes adding into ArrayList of O(n) in worst case, while adding is O(1) operation in LinkedList. ArrayList also needs to be update its index if you insert something anywhere except at the end of array.
2. Removal also better in LinkedList than ArrayList due to same reasons as insertion.
3. LinkedList has more memory overhead than ArrayList because in ArrayList each index only holds actual object (data) but in case of LinkedList each node holds both data and address of next and previous node
4. Both LinkedList and ArrayList require O(n) time to find if an element is present or not. However we can do Binary Search on ArrayList if it is sorted and therefore can search in O(Log n) time.

Thank you..!!!!