My Notes Day 3

 Linked Lists:

Series of nodes, each node has a single pointer to the next node and in the last node's case a null pointer representing that there are no more nodes in linked list.

Linked list will always maintain head and tail pointers so that insertion at either head or tail of the list is a constant time operation. Random insertion is excluded from this and will be a linear operation.

1. Insertion - O(1)
2. Deletion - O(n)
3. Searching - O(n)

Here we chose to always maintain pointers to the nodes at the head and tail of the linked list and so performing a traditional insertion to either front or back of linked list is O(1) operation. An exception to this rule is performing insertion before a node that is neither the head nor the tail in a singly linked list. When the node we are inserting before is somewhere in the middle of the linked list (the random insertion) the complexity is O(n). In order to add before the designated node we need to traverse linked list to find that node's current predecessor.

The linked list is dynamically resized, thus it incurs no copy penalty like an array or vector which would eventually incur and insertion is O(1).

Singly linked list:

Each node that makes up singly linked list consists of a value and a reference to next node (if any) in the list.

*Insertion:

In general when people talk about the insertion with respect to linked lists of any form they implicitly refer to the adding of node to the tail of the list. When you use an API of DSA and you see a general purpose method that adds a node at the list you can assume that you are adding node to the tail of the list not head. Adding node to a singly linked list has only 2 cases:

1. Head = NULL in which case the node we are adding is now both the head and the tail of the list or
2. We simple need to append our node onto the end of the list updating the tail reference appropriately.

=>Algorithm

1. Add(value)
2. Pre: value is the value to add to the list
3. Post: value has been placed at the tail of the list
4. n <- node(value)
5. if head = NULL
6. head <- n
7. tail <- n
8. else
9. tail.Next <- n
10. tail <- n
11. end if
12. end Add

*Searching:

Searching a linked list is straight forward. We simply traverse the list checking the value we are looking for with the value of each node in the linked list.

=>Algorithm

1. Contains(head, value) 
2. Pre: head is the head node in the list
3. value is the value to search for
4. Post: the item is either in the linked list, true; otherwise false
5. n <- head
6. while n != NULL && n.value != value
7. n <- n.Next
8. end while
9. if n!= NULL
10. return false
11. end if
12. return true
13. end contains

*Deletion:

Deleting a node from a linked list is straightforward but there are a few cases we need to account for:

1. The list is empty or
2. the node to remove is only node in linked list or
3. we are removing the head node or 
4. we are removing the tail node or 
5. the node to remove is somewhere in between head and tail or
6. the item to remove doesn't exist in the linked list

The algorithm whose cases we have described will remove a node from anywhere within a list irrespective of whether node is head etc. If items will only ever be removed from the head or tail of the list then you can create much more concise algorithm.

=>Algorithm

1. Remove(head, value)
2. Pre: Head is the head node in the list
3. value is the value to remove from the list
4. Post: Value is removed from the list, true; otherwise false
5. if head = NULL
6. //case 1
7. return false
8. end if
9. n <- head
10. if n.value = value
11. if head = tail
12. //case 2
13. Head <- NULL
14. tail <- NULL
15. else
16. //case 3
17. head <-head.Next
18. end if
19. return true
20. end if
21. while n.Next != NULL & n.Next.value != value
22. n <- n.Next
23. end while
24. if n.Next != NULL
25. if n.Next = tail
26. //case 4
27. tail <- n
28. end if
29. //this case exists only case 5 if conditional on line 25 was false
30. n.Next <- n.Next.Next
31. return true
32. end if
33. //case 6
34. returm false
35. end remove

*Traversing the list:

You start at the head of the lust and continue until you come accross that NULL. 2 cases 

Case 1: node != NULL, we have exhausted all nodes in the linked list or

Case 2: We must update the node reference to be node.Next

The algorithm described is very simple one that makes use of while loop to check the first case.

=> Algorithm

1. Traverse()head
2. Pre: head is the node in the list
3. Post: the items in the list have been traversed
4. n <- head
5. while n != 0
6. yield n.value
7. n <- n.Next
8. end while
9. end traverse

*Traversing the list in reverse order

Traversing a singly linked list in forward manner (left to right) is simple; if same has to be done in reverse way (right to left) This becomes O(n^2)

=> Algorithm

1. Revers traversal(head, tail)
2. Pre: head and tail belong to same list
3. Post: the items in the list have been traversed in reverse order
4. if tail != NULL
5. curr<-tail
6. while curr!=head
7. prev <- head
8. while prev.Next != curr
9. prev<-prev.Next
10. end while
11. yield curr.value
12. curr<-prev
13. end while
14. yield curr.value
15. end if
16. end reverse traversal

*Doubly linked list:

Traversal and reverse traversal is very easy in doubly linked list. Doubly linked lists are very similar to singly linked list. The only difference is that each node has a reference to both the next and previous nodes in the list. Similarly for the searching and traversal.

Summary:

Using data structures like an array would require you to specify the size upfront exceeding that size involves invoking a resizing algorithm which has linear run time. You should also use linked lists when you will only remove nodes at either the head or tail of the list to maintain a constant run time. This requires maintaining pointers to the nodes at the head and tail of the list but the memory overhead will pay for itself if this an operation you will be performing many times.

What linked lists are very good at is random insertion. Accessing nodes by index and searching, at the expense of little memory and a few more read writes you could maintain a count variable that tracks how many items are contained in the list so that accessing such a primitive property is a constant operation, you just need to update count during the insertion and deletion.