Now that you've been introduced to measuring the complexity of algorithms, it's time to start looking at one of the most used data structures: linked lists!
A LinkedList is a class in Java that defines a very fundamental abstract data type in computer science.
Why are Linked Lists Fundamental
Linked lists are often used under the covers for many other abstract data types.
What's funny and interesting about linked lists is their simplicity. A linked list is simply one object that points to another object of the same type (hence the abstract nature of this data structure).
What is an Abstract Data Structure
An abstract data structure is a data structure that differs from a traditional (concrete) data structure in that it is defined by its behavior rather than by its physical structure.
For instance, both an Array and ArrayList in Java are traditional (concrete) data structures. Their "physical" structure defines them.
Whereas LinkedList, Stack, Queue, HashMap, trees and many other abstract data structures (you'll be introduced to each of these in the upcoming lessons) are defined by rules and/or behavior that you place on objects. This will make much more sense shortly.
Big O of a LinkedList
If adding and removing from the front of the list, it's constant time - aka $`O(1)`$. $`O(1)`$ is about as good as it gets. To search a LinkedList it's often necessary to scan the entire list - therefore $`O(n)`$ which isn't horrible.
As a result, a LinkedList has, at most, a linear growth complexity, which is much better than exponential! This explains why it helps form the building blocks of other data structures.
How Does a LinkedList Work
At first, it may seem like the LinkedList is a complicated structure to understand, but it is really based on only a few key functionalities listed below.
Dynamic Data Structure
A LinkedList is a dynamic data structure. No size restrictions or sizing implications exist when working with a LinkedList. You can make it as large or as small as you want, and it can grow and shrink naturally to fit the use case.
The Head Node
When working with a LinkedList, the only Node you must always keep track of is the head node. The "head node" is a reference to the first node in the list. As long as you have access to the head node, you can access the entire list behind it. You lose the whole list if you lose track of the head node.
No Direct Random Access
A LinkedList does NOT allow direct random access. In an array, you can access an element at the 4th or 567th index immediately and directly. In a LinkedList, this is not the case. In a LinkedList, you must start at the head node and traverse the list until you find the element you want. This makes the Big O for "Access & Search" $`O(n)`$.
How to Use a LinkedList
The theory is great, but maybe some examples might help ;)
Imagine you have a simple LinkedList like the one below, where A links to B, which links to C, and so on:
A -> B -> C -> D
How do you delete B from this list? So that it now looks like A -> C -> D?
You delete B from this list by pointing A at C. And the way that you do that is with a little code that looks like this:
a.next = a.next.next;
Now, this looks a little funky, but it works perfectly. You're saying a.next (initially pointed at B) is now equal to a.next.next. This works because a.next (initially pointed at B) has its own .next variable, which points at C. So you're saying you want a.next to point at whatever b.next is currently pointing at. Thanks to this, you have arrived at the desired LinkedList.
A -> C -> D
Example LinkedList
Examine the Node class below, which is the core of a LinkedList:
public class Node<T> {
//The Node list is generic and holds a piece of "data"
T data;
// the Node class (this class) has an instance variable
// which points to another Node object
Node next;
public Node(T data) {
this.data = data;
this.next = null;
}
}
Notice how the class above, Node, has an instance variable within of type Node? This means that one Node object has a link to another Node object (called next). Because of this, you can now do something like this:
public class SimpleLinkExample {
public static void main(String[] args){
// create a simple Node and pass in a Person object
Node<Person> node = new Node(
new Person("Coding", "Nomad1", "[email protected]"));
// set the "next" variable inside the node object to new Node
node.next = new Node(
new Person("Coding", "Nomad2", "[email protected]"));
}
}
See how you're able to essentially chain these Node objects together using the next variable? Now, as you continue to link more and more nodes onto each other (using the next variable), you're creating your own Abstract Data Structure (ADS). In this case, a LinkedList. Pretty interesting, eh?!
Types of LinkedList
There are three main types of linked lists.
1. Traditional LinkedList
The image below details the architecture of a traditional LinkedList in Java.
In the real world, you will use a LinkedList class to interact with these nodes rather than directly, as you see above. But the principle remains the same.
2. Doubly LinkedList
There are singly linked lists and doubly linked lists. In a singly linked list - a (traditional) LinkedList, the linking (aka pointing) only happens in one direction (as you see in the image above).
Whereas in doubly-linked lists, the linking happens in both directions. This is done by simply having a next variable that links to the next node and a prev or "previous" variable that points to the previous node. The image below shows how this works.
There is also a variation of a doubly linked list which contains a tail reference. As in previous examples, the head points to the first node in the list, but here a tail variable points to the last node in the list. These references can simplify operations like insertion and deletion at both ends of the list.
3. Circular Doubly LinkedList
There are also circular linked lists. A circular list is simply a LinkedList where the "tail" node (aka the last node in the list) points at the head node - effectively making it circular.
Now that you're getting a groove for what a LinkedList is, it's about time to discover some of the many ways in which they can be applied!
If you'd like to continue learning about Linked Lists, check out the following resources in the Data Structures & Algorithm course:
Summary: Linked Lists in Java
- A
LinkedListis a fundamental abstract data structure in Java - Linked lists are used as the foundation for many abstract data structures
- An abstract data type is defined by its behavior rather than its structure
- Key defining aspects of a
LinkedList: dynamic data structure, contains a headNode, and offers no direct random access
Big O of LinkedList
- Best Case (Insert & Delete): $`O(1)`$
- Worst Case (Access & Search): $`O(n)`$
Types of LinkedList
- Traditional (Singly-Linked)
- Doubly-Linked
- Circular Doubly-Linked