## Data Structure Name: LinkedLists - #### Description: - Arrays are inefficient for insert operations since each element is moved individually to a new location in memory. LinkedLists were created to avoid these expensive operations. Each value of array is linked to the memory location of the next element in the array. - #### Variations: - Singly-linked List - Doubly-Linked List - #### Diagram: - #### General Use: ## Key Considerations - #### Properties: - #### Implementation Details: | | | Singly Linked List <br>[[Big O - Time Complexity]] | Doubly Linked List <br>[[Big O - Time Complexity]] | | --------- | ------------------- | -------------------------------------------------- | -------------------------------------------------- | | Access... | *by index* | O(N) | O(N) | | Add... | *before first node* | O(1) | O(1) | | | *after given node* | O(1) | O(1) | | | *after last node* | O(N) | O(1) | | Delete... | *the first node* | O(1) | O(1) | | | *a given node* | O(N) | O(1) | | | *the last node* | O(N) | O(1) | | Search... | *a given node* | O(N) | O(N) | - #### General Tips - Always examine if the node is null before you call the next field. - Getting the next node of a null node will cause the null-pointer error. For example, before we run fast = fast.next.next, we need to examine both fast and fast.next is not null. - If you are using .next in your loop, you loop need to check that the .next node exists - Carefully define the end conditions of your loop. - Run several examples to make sure your end conditions will not result in an endless loop. And you have to take our first tip into consideration when you define your end conditions. - #### Special Properties - Finding the Middle of LinkedList - Have two pointers, use one to travel to end twice as fast, then slow will be in middle ## Specific Use Cases - Finding a Cycle - To find a cycle use [[Floyd's algorithm]], which states that if a cycle exists then a slow and fast pointer will converge at some point if they are traveling at steps of 1 and 2 - To find the start of the cycle: - Find the point at which they converge using Floyd's algorithm - The distance from the converged point to the head is the length - Intersection of Two Linked Lists - When the two lists are concatenated, you can increment from the start of each list and they will intersect at the intersection node or end up null at the end - ![[LinkedListIntersection.png]] -