Linked Lists

Linked Lists Overview

• A linked list is a sequence of nodes that are connected ("linked") to each other. Each node references the next node in the link.
• Linked lists are linear data structures and have a sequence and order to how they are constructed and traversed.
• Arrays need specific amounts of memory when created, all in one continued block. They are "static data structures"
• Linked lists don't need one specific amount of memory when created and can instead the memory they use can be spread all over the place. They are "dynamic data structures".
• Two types: Singly LL & Doubly LL
• Singly LL: refers to the number of references that the node has. Singly LL only have one reference, which points to the next node in the list.
• Doubly LL: means that there are two references w/in the node. There is a reference to both the "next" and "previous" nodes.
• Node: individual links that populate a linked list containing the data for each link.
• "Next": All nodes have the "next" property that contains the reference to the next node.
• "Head": the reference to the first node in the linked list.
• "Current": the reference to the node that is currently being looked at. Usually used when traversing through a fully linked list. Usually we would reset the "current" to the "head" to make sure we are starting from the beginning of the linked list.

Traversing Linked Lists

• We use "next" in each node to tell us where the next reference point is. It lets us extract the data correctly.
• We can't use a "foreach" or "for" loop, but we can use a "while()" loop, which allows us to check that the "next" node in our list is not "null".
• Using the "current" node is useful because it tells us where we are and lets us traverse forwards until we hit the end of our linked list.
• The Big O of time for "find" is O(n), because the node we are looking for will be the last node in the linked list. "n" represents the number of nodes in the linked list. The Big O of space for "find" is O(1) since there is not added space being used compared to what we already had.

Adding a Node to our Linked List

• The order of operations is important and we need to make sure all of our references to each node is correctly assigned.
• No mater how many nodes that our LL has, it will always be O(1) time and space as it takes the same amount of time to add on a new node to the start of our list. No added resources need be used.
• Remember that when making our node class to require a value to be passed in so that each node has a value.
• We should also require that at least one node gets passed in once we instantiate. That first node is where our "head" and "current" point to.