The Linked List Data Structure
Why Data Structures?
We will start from the very beginning. What is an algorithm?
We provide some input, such as an address or a person’s name, and give it to the computer. We expected to receive an output, in this case, a map with a direction to that address or a LinkedIn profile associated with that name.
The process that turns an input into output is called an algorithm.
As programmers, it is our job to make this process as efficient and accurate as possible. And to optimize the process, we need to organize the data (input) into a particular form (data structure) so that it can be retrieved (output) and used most efficiently.
How should we measure performance?
We need to consistently ask ourselves: how much time is required to process the algorithm and how much space do we need for its computation? We process and look for the best way to organize the data (in terms of time & space) to be better processed based on the input provided.
Take an example of a search engine, like Google; they’re managing huge amounts of data using the link structure to order the search results.
Common Data Structures
- Static and dynamic arrays
- Linked lists
- Stacks
- Queues
- Heaps/Priority Queues
- Binary Trees/Binary Search Trees
- Union find/Disjoint Set
- Hash tables
- Fenwick trees
- AVL trees
We will look at the linked list today. Before jumping into it, let’s review our old friend “Arrays” since they share many similarities.
Arrays
Arrays are one of the most basic forms to store data. Each element of an array has an index that starts at 0. You can instantaneously access and modify an element with the index number. If the location is unknown, we will need to do a sequential lookup to check the elements one by one (starting at index 0) until we find it. Arrays are useful because of their simplicity and instant access to properties.
Linked Lists
A linked list is a collection of objects linked together by references. The linked objects are the main component called nodes and the references that linked them together are called pointers.
Below is a simple diagram of a basic linked list — “Singly” linked list. We can see that each node contains one or more data fields and a pointer pointing to the next node. The first node is called the head, and the last node is the tail. The tail contains a null reference to indicate the end of the list.
A use case of Doubly linked lists is our web-browsers. They create a linked list of web pages visited so that when you check history (traversal of a list) or press the back button, the previous node’s data is fetched.
Array vs Linked List
Types of Linked Lists
- Linear(singly) Linked List: Linear data structures (e.g. stack, queue) are easily implemented.
- Doubly-linked list: has two references from each node, one to the next node and another to the previous node.
3. Circular Linked List: with multiple links from nodes.
I hope this brief introduction of linked lists helps you gain a better understanding of linked list data structure.