Linked Lists
Linked Lists / Slide 2
List Overview
Linked lists
What is a Linked List
Basic operations of linked lists
Insert, search, delete.
Variations of linked lists
Circular linked lists
Doubly linked lists
Linked Lists / Slide 3
What is a Linked List
A linear data structure.
Consists of nodes, each containing data and a
reference to the next node.
Unlike arrays, doesn't require contiguous
memory allocation.
Linked Lists / Slide 4
Linked Lists
A B C
Head
A linked list is a series of connected nodes
Each node contains at least
A piece of data (any type)
Pointer to the next node in the list
Head: pointer to the first node node
The last node points to NULL A
data pointer
Linked Lists / Slide 5
Basic Operations of a Linked List
In general, every Linked List structure will
have to support three main basic operations:
Search — search for an element based on its
value/data stored or location.
Insert — Insert new element to the list.
Delete — Remove an element based on its value
or location from the list
Linked Lists / Slide 6
Using the LinkedList Class
import java.util.LinkedList;
This line imports the LinkedList class from the
java.util package so that you can use it in your
program.
Linked Lists / Slide 7
Create a LinkedList
LinkedList<String> cars = new LinkedList<String>();
This Create a LinkedList of Strings named "cars“
LinkList can be of any primitivate data type
Linked Lists / Slide 8
Methods in a LinkedList Class
Linked List provides several methods to do
certain operations more efficiently:
Linked Lists / Slide 9
Add Elements to a LinkedList
The add() method is used to add an element
at the tail of the list
// Add elements to the LinkedList
cars.add("Volvo");
cars.add("BMW");
cars.add("Ford");
cars.add("Mazda");
Linked Lists / Slide 10
Variations of Linked Lists
Circular linked lists
The last node points to the first node of the list
A B C
Head
How do we know when we have finished traversing
the list? (Tip: check if the pointer of the current
node is equal to the head.)
Linked Lists / Slide 11
Variations of Linked Lists
Doubly linked lists
Each node points to not only successor but the
predecessor
There are two NULL: at the first and last nodes in
the list
Advantage: given a node, it is easy to visit its
predecessor. Convenient to traverse lists backwards
A B C
Head
Linked Lists / Slide 12
Array versus Linked Lists
Linked lists are more complex to code and manage
than arrays, but they have some distinct advantages.
Dynamic: a linked list can easily grow and shrink in size.
We don’t need to know how many nodes will be in the list. They
are created in memory as needed.
In contrast, the size of a C++ array is fixed at compilation time.
Easy and fast insertions and deletions
To insert or delete an element in an array, we need to copy to
temporary variables to make room for new elements or close the
gap caused by deleted elements.
With a linked list, no need to move other nodes. Only need to
reset some pointers.
Linked Lists / Slide 13
Exercise
You are given the task of implementing a singly linked list in
Java. In your main method, create an instance of the Linked List
class, insert the elements "A," "B," "C," "D," and "E" into the list,
and then perform the following operations:
Print the list.
Check if the list contains "B" and print the result.
Remove "C" from the list.
Print the modified list.
