What is a Linked List?
Often used to implement other data structures, such as stacks, queues and trees, a linked list is a linear data structure. Forming what can be thought of as a linked chain, a linked list is a sequence of nodes. Each node stores its own data and a pointer (address) to the location of the next node. The last link in a linked list points to null, indicating the end of the chain.
Linked List == Chain of Links
Is it like an array?
Although similar to an array in its approach to sequence and order, a linked list is not restricted to a declared number of elements. Also unlike an array, where each array element is stored contiguously (each element has a consecutive memory address), linked list elements are not stored contiguously. Therefore, in contrast to an array, linked list elements can be inserted and removed without reallocation of memory.
Array objects stored at consecutive memory addresses vs. linked list objects stored anywhere.
Costs: Array vs. Linked List
Big-O notation is a way of describing (and comparing) how many operations an algorithm (or, in this case, a data structure) needs to perform some task.
Big-O visualized.
Cost of accessing an object:
Array == O(1) vs. Linked List == O(N)
Cost of insertion/deletion:
Array == O(N) vs. Linked List == O(1)
Array?s are quicker at accessing objects, but Linked List?s are quicker at inserting and deleting objects.
For more information on Big-O notation check out the Big-O Cheat Sheet. It?s a great resource.
Important Points to Remember About a Linked List
- Each link in a linked list is an object (also called an element, node, etc.).
- Each object holds a reference (an address) to the location of the next object.
- The last link in a linked list points to null, indicating the end of the list.
- A linked list can grow and shrink dynamically at run-time (the time at which your program is running, after it has been compiled), limited only by the amount of physical memory available.
Advantages of a Linked List
- Insertions and deletions are quick.
- Grows and shrinks as needed.
Disadvantages of a Linked List
- Random access is slow. Objects in a linked list must be accessed sequentially, therefore, it can be slow to access a specific object.
- Memory is a concern. Each object in a linked list requires data as well as one (or more) pointers to other objects in the linked list. Using significantly less memory, each object in an array only requires data.
When to Use a Linked List?
- You don?t need random access to any specific elements.
- You need to do constant insertions and deletions.
- You?re not sure how many items will be in the list.
Doubly Linked Lists
A doubly linked list (or double linked list) is a more complex implementation of a linked list. It requires more memory, but accessing objects is easier. Accessing from the first or leftmost object (called the ?head?) costs as much as accessing from the last or rightmost object (called the ?tail?). Each object in a doubly linked list contains two references (unlike one in a basic linked list) to the previous and to the next node in the sequence.
A basic linked list vs. a doubly linked list.
Let?s Make a Linked List in Java
Java, as a programming language, focuses on code reusability through classes and objects. A class is basically a blueprint or template for an object. Though you can build your own custom classes for a linked list implementation, Java does offer a convenient built-in LinkedList class.
For this short example, Java?s built-in LinkedList class is used. It should be noted that, according to the the official documentation, all operations offered by the built-in class perform as expected for a doubly-linked list implementation. Additionally, the LinkedList built-in class is technically a list implemented using a linked list. In contrast, Java?s built-in ArrayList class is technically a list implemented using an array. Choosing which to use in your program is dependent on both your goals and memory availability.
Example: Make an empty linked list, store the values 1, 2 and 3 in it and print the values out.
When using Java?s built-in LinkedList class, you should start by importing the LinkedList class and creating an empty linked list. For this example, an empty linked list of integers is created.
import java.util.LinkedList;public class MainDriver { public static void main(String args) { LinkedList<Integer> Numbers = new LinkedList<Integer>(); }}
There?s a variety of built-in methods that you can use when working with your new linked list. The code snippet below adds 1, 2 and 3 to the linked list.
import java.util.LinkedList;public class MainDriver { public static void main(String args) { LinkedList<Integer> Numbers = new LinkedList<Integer>(); Numbers.add(1); Numbers.add(2); Numbers.add(3); }}
It?s also very simple to iterate over a linked list and print out all the data.
import java.util.LinkedList;public class MainDriver { public static void main(String args) { LinkedList<Integer> Numbers = new LinkedList<Integer>(); Numbers.add(1); Numbers.add(2); Numbers.add(3); for (Integer n : Numbers) { System.out.println(n); } }}
For additional information on Java?s built-in LinkedList class, check out the official documentation.
