LinkedList
A LinkedList is a linear data structure. You already know some linear data structures, such as arrays, where each element has a value and position within the whole. A LinkedList consists of a number of nodes, which contain a value and a pointer which points to the next node in the list.
Image courtesy GeeksForGeeks
Nodes... What are they?
The above image shows a 4-node linked list. Each node, including the first and last, have pointers. The first node, the head, contains a value and points to the next node. The last node, the tail, points to null, since it is the last node.Null is a value in java which means empty or nothing.
Note: it is possible for the tail node to point to the head node, in which case you would have a circular LinkedList(covered next).
LinkedList implements two interfaces, List and Deque. List is an interface that is implemented by structures such as ArrayList and Vector(this is a little advanced). Deque extends the Queue interface, which is where LinkedList gets its order from. You can think of LinkedList as a list with a queue, or an order.
There are singly linked lists and doubly linked lists. In singly linked lists, each node has only one pointer which creates a chain in one direction. In other words, you cannot go backwards in a singly linked list. Doubly Linked Lists go in both directions (covered in a later section), and the Java LinkedList class is an example of a doubly linked list.
Implementation
To implement a LinkedList:
import java.util.LinkedList; class Main { public static void main(String[] args) { LinkedList<String> a = new LinkedList<String>(); // adding items a.add("One"); a.add("Three"); a.add(1, "Two"); System.out.println(a); // setting items a.set(1, "2") // removing items a.remove("2"); a.removeFirst(); a.remove(0); System.out.println(a); } }
Note that you need to import LinkedList from java’s utility package, or use import java.util.*
Methods
The three main methods for LinkedLists are add, set, and remove.
add(Object) or add(index, Object) - Adds the object to the index of the list and shifts every value after it over one. If no index is specified the object is added to the end.
set(index, Object) - Changes the value of the node at the index to the given object.
remove(index), remove(Object), removeFirst(), removeLast() - Removes the node at the specified index. If an object is given, this only removes the first instance of that object in the list. The last two methods remove the node at the start or end of the list.
Refer to the documentation for other LinkedList methods: https://docs.oracle.com/javase/7/docs/api/java/util/LinkedList.html
Copyright © 2021 Code 4 Tomorrow. All rights reserved.
The code in this course is licensed under the MIT License.
If you would like to use content from any of our courses, you must obtain our explicit written permission and provide credit. Please contact classes@code4tomorrow.org for inquiries.