Code 401: Class 05 - Linked Lists
- Sequence of nodes that are connected to each other, each references the next
- Singly each node has one reference pointing to the next node
- Doubly each node references both the previous and next node
- Next property on a node that references the following node
- Head first node in a list
- Current property that indicates which node is currently being viewed
While loop is the best method for traversing a linked list- Big O of Linked list
- Linear data structure sequence and order to how they are traversed
- Dynamic data structure can shrink and grow in memory to fit the present data
- Single node contains data and pointer to next node
- List goes from Head to null
- Circular linked list tail of the list (conventionally the head), next node is the beginning of the list
- Big O method for evaluating the performance of an algorithm
- O(1) function takes constant time and memory regardless of how many elements are run through an algorithm
- O(n) function linear growth in time and memory as number of inputs grows
- O(n^2) function exponential growth in time and memory as inputs grow
- To add a node to the beginning of a linked list O(1) constant
- Find head node
- Make new node, set pointer to current first node
- Make head node point to the new node
- To add new node at end of list O(n) linear
- Find last node
- Make new node and set pointer to null
- Make last node point to new node
Return to reading-notes Deployed Site
Return to reading-notes Mark Down