loading...

Linked Lists

jjb profile image JB Updated on ・2 min read

CS Level Up Series (30 Part Series)

1) CS Level Up Series Introduction 2) Dynamic Arrays 3 ... 28 3) Linked Lists 4) Stacks 5) Queues 6) Hash Tables 7) Binary Search Trees 8) Binary Heaps 9) Priority Queues 10) Graphs 11) Tries 12) Binary & Bit Manipulation 13) Common Sorting Algorithms 14) Searching Algorithms 15) Permutations, Combinations, & Subsets 16) NP-Complete & Fibonacci Heap 17) Detecting Graph Cycles With Depth-First Search 18) Finding Shortest Paths In Graphs (using Dijkstra's & BFS) 19) Topological Sorting of Directed Acyclic Graphs (DAGs) 20) Finding Articulation Points & Bridges in Undirected Graphs 21) Finding Strongly Connected Components in Directed Graphs using Tarjan's Algorithm 22) Checking If An Undirected Graph Is Bipartite 23) Extending An Iterator 24) Union-find (Disjoint-set) 25) Minimum Spanning Tree (Kruskal's Algorithm) 26) Sliding Window Technique 27) String Searching Using Rabin-Karp 28) Fenwick Tree (Binary Indexed Tree) 29) Dynamic Programming 30) Traveling Salesman Problem

Resources

  1. Linked list overview and implementation
  2. Linked list overview
  3. Detailed overview and implementation

Takeaways:

  • Insertions and deletions are O(1) (constant time).
  • Searching for an element is O(n) (linear), and not cache friendly*
  • Space is O(n). But it's important to note that the effective memory is double that of a regular array. This is because each node contains value/data and a reference/pointer to the next node. This means Linked Lists use an extra 4 bytes of memory for each element.
  • There are 3 common types of Linked Lists: singly linked, doubly linked, and circularly linked.
  • Each node in a Singly Linked List has a pointer to the next node. This means traversal can only happen in one direction.
  • Doubly Linked Lists have two pointers per node, one for the next node and one for the previous node. Traversal can be in both directions.
  • In Circular Linked Lists the tail (last node) has a pointer to the head node (first node).
  • Although it is common for Linked List implementations to only maintain a reference to the head node, some implementations also keep track of the tail node.

*Linked Lists, unlike Dynamic Arrays, aren't required to be stored in continuous blocks of memory. This means each node in a Linked List does not have to be stored next to other nodes belonging to the same Linked List. For this reason, the CPU cannot effectively cache the contents of a Linked List as well as it can an array.

Here's the finished implementation of a Singly Linked List with test code:

As always, please let me know if you noticed an error with anything in this post.

CS Level Up Series (30 Part Series)

1) CS Level Up Series Introduction 2) Dynamic Arrays 3 ... 28 3) Linked Lists 4) Stacks 5) Queues 6) Hash Tables 7) Binary Search Trees 8) Binary Heaps 9) Priority Queues 10) Graphs 11) Tries 12) Binary & Bit Manipulation 13) Common Sorting Algorithms 14) Searching Algorithms 15) Permutations, Combinations, & Subsets 16) NP-Complete & Fibonacci Heap 17) Detecting Graph Cycles With Depth-First Search 18) Finding Shortest Paths In Graphs (using Dijkstra's & BFS) 19) Topological Sorting of Directed Acyclic Graphs (DAGs) 20) Finding Articulation Points & Bridges in Undirected Graphs 21) Finding Strongly Connected Components in Directed Graphs using Tarjan's Algorithm 22) Checking If An Undirected Graph Is Bipartite 23) Extending An Iterator 24) Union-find (Disjoint-set) 25) Minimum Spanning Tree (Kruskal's Algorithm) 26) Sliding Window Technique 27) String Searching Using Rabin-Karp 28) Fenwick Tree (Binary Indexed Tree) 29) Dynamic Programming 30) Traveling Salesman Problem

Posted on Nov 4 '19 by:

Discussion

markdown guide