LINKED LIST -- BIG(O) FOR ADD & DELETE METHODS 2014
I. ADD methods : LinkedList :
Add methods - BIGO
1. InsertFirst(target) BigO(1)
2.InsertLast(target) BigO(1)
3 Insert(target) BigO(N)
*********************************************************************************************************************
For InsertFirst(target)-- this method inserts at the front of the list - no loop needed. Points head to the newnode and newnode to what head is referencing
BigO Final for InsertFirst() = BigO(1)
************************************************************************
For InsertLast(target)-- this method inserts at the end of the list. Creates the node and assigns Tail to point(reference) to it.
BigO Final for InsertLast() = O(1) = BigO(1)
Insert(target) - This method inserts anywhere on the list.
Calls find(target) to place current at the node to be deleted. Cannot get an O( lgn) for the search, even when the linked list is sorted. To get an O( lgn), as in Arraylist, you need to go to the middle of the array. You can do this because you know the size of the array, and you divide that by two. (You pre -allocate the memory)
However, in a LinkedList, nodes are not stored next to one another so you don’t know where the middle is. Nodes are added and stored in various locations. So no way to eliminate ½ of them as Binary Search does with each iteration of the search.
So breaking down the steps for Insert(target) for LinkedList:
Find(target) = N -- traverses the whole Linked List worst case
Insert when found = O(1). – target can be added between any two nodes,
Big(O) Final for Insert() = O(N) (find)+ O(1)(insert) = BigO(N)
WE do not consider the sorted linked list because it has the same big O as the unsorted linked list
II. Add methods - ArrayList -Unsorted : BIG(O)
1. Insert(target) BigO(1) -
2. InsertFirst(target) BigO(N)
3. InsertLast(target) BigO(1) Not usually implemented
**************************************************************************
Insert(target) - UNSORTED - . Just adds to the end of the list BigO(1)
***************************************************************************
InsertFirst(target) – inserts at beginning of the list - have to move all the values down before inserting it -- BigO(N
***********************************************************************************
III. Add methods - ArrayList Sorted : BIG(O)
1. Insert(target) BigO(N) - For Insert(target) - You get a O(Lg N) to find the location where to insert using a Binary Search– but worse case you have to move all of the items down to put the new value in so : LgN(find) + N to Insert the value = O(N)
To Find location – Uses Binary Search - goes to the middle of the array and to the middle of left or right side etc. You can do this because you know the size of the array and you divide that by two.
***********************************************************************************
The BigO for delete methods for Linked List is same for unsorted and sorted
IV. Delete methods - LinkedList : BIGO
RemoveFirst(target) BigO(1)
RemoveLast(target) BigO(N)
Remove(target) -anywhere BigO(N)
*******************************************************************************************************************************************************************
Remove(target) - This method removes anywhere on the list.
Calls find(target) to place current at the node to be deleted.
It is not possible to get an O( lgn), for the search, even when the linked list is sorted. (See above in Insert Methods)
So breaking down the steps for Delete(target) for LinkedList:
Find(target) = N -- traverses the whole Linked List worst case
Delete(target) when found = O(1). – Uses current and previous to remove the node
BigO Final for Remove() = O(N) + O(1) = BigO(N)
************************************************************************
DeleteFirst(target) -- this method removes at the front of the list - no loop needed. Advance Head to the next node, cutting off the original first node
BigO Final for DeleteFirst() = O(1) = BigO(1)
************************************************************************
For RemoveLast(target)-- this method removes at the end of the list - same as Remove above. Must call find() and place current and previous at the last nodes – you need a pointer to the next to last node and find puts previous at the next to last node. Then set previous.next to null - last node is GONE!
BigO Final for InsertLast() = O(N)(Find) + BigO(1) ( to remove it) = O(N)
**************************************************************
IV Delete methods - ArrayList -Unsorted :
RemoveFirst(target) BigO(1)
removeLast(target) BigO(1)
Delete( target) Big O(N)
For removeFirst(), swap in value in last index to the first index. Set value in last index to null
For removeLast(), set value in last index to null ( there is reference at the end of the list)
For Delete(target) - BigO(N) to Find the target, BigO (N) to move values up or down
IV Delete methods - ArrayList -sorted :
For Delete(target) – You can get a O(Lg N) to find location where to remove with a Binary Search– But worse case you still have to move all of the items down to put the new value in so : LgN(find) + N to remove the value = O(N)
*********************************************************************
http://www.csc.villanova.edu/~helwig/BigOLinkedListVsArrayList.doc
1