
With 2020 we are going to look at a new aspect of programming: data structures. It is often the case that everyone uses structures provided by the various programming languages. The objective will be to have a general idea of how they work and their internal mechanisms. Often we will give a version not quite the same as the one actually implemented, but in the end we will still have an overview of how the structure works.
In particular, today we are going to deal with a rather difficult topic for many people: Linked Lists.
Let's take a closer look.
A Linked List is composed of nodes. A node is the set of data it must represent and the pointer to its next. This means that each node will have a field containing the address of the next element in the list.
Let's have a look to a picture:
Let's see how the node is composed of a generic data field that represents all the information it should contain and a next field, which represents the pointer to the next node.
Why do we need the field next?
The idea is not to need a contiguous space in RAM, so you choose to allocate a number n of nodes where there is space available. We therefore obtain the advantage of a dynamic structure also from the point of view of memory occupation.
Implementation of the Node class
In this implementation we assume that the node information is a whole number. It can easily be replaced with more complex data types.
public class Node { int data; Node next; //Constructor to create a new node // Initialize next to null by default Node(int data) { this.data = data; this.next=null; } }
The class is very simple in its implementation, in fact it has only one constructor that only initializes the data field and sets the next default field to null. For completeness, I preferred to make the initialization of the next one explicit.
LinkedList class
Let's go and see some operations that we can perform on the linked lists.
Creation, insertion and printing
import java.io.*; // Java program to implement // a Singly Linked List public class LinkedList { private Node head; // head of the list // method to insert a new node // returns a new list public static LinkedList insert(LinkedList list, int data) { // create a new node with the data given Node toInsert = new Node(data); // if the list is empty, // the new node becomes the head if (head == null) { head = toInsert; } else { // Otherwise scrolls the list down to the last node // and insert the new node there Node last = head; while (last.next != null) { last = last.next; } // insert the new node as the last last.next = toInsert; } // Returns the new list by returning the pointer to the head return list; } // method to print a list public static void printList(LinkedList list) { Node curr = head; // Browse the concatenated list while (curr != null) { // print the data contained by the current node System.out.print(curr.data + " "); // passes to the next node curr = curr.next; } } public static void main(String[] args) { /* begin with an empty list */ LinkedList list = new LinkedList(); // insert values list = insert(list, 11); list = insert(list, 21); list = insert(list, 31); list = insert(list, 41); list = insert(list, 51); list = insert(list, 61); list = insert(list, 71); list = insert(list, 81); // print the list printList(list); } }
Let's understand better what happens. The insert method shown above performs what we call queued insertion, making the node to be inserted the last one.
We can distinguish two cases: the empty list and the non-empty list.
In the case of an empty list, the node to be inserted becomes the head of the list, as well as the only node in the collection.
In the case of a non-empty list, you scroll the list until you find the last node. Then the next field of the last node is set with the address of the node to be inserted. In this way we will get a new list whose last node is the node we want to insert.
As far as printing is concerned, we'll just do a cycle that iterates until the elements to be printed are finished. At each iteration, we print the data field of the node being examined.
Let's see a drawing.

Deletion by key
The idea is that, given the data to be removed from the list, we delete the first occurrence we find. We will follow the following steps:
- We search for the occurrence of the element;
- If I find the item, I have three cases:
- The found item is the head of the list, so you update the head pointer and let the garbage collector take care of the node you can't reach;
- The found item is inside the list or at the end, so you will have to search for the previous item if found and update its next pointer.
- If I don't find the item, I do nothing.
Let's see the code:
public
static
LinkedList deleteByKey(LinkedList list,
int
key)
{
Node currNode = list.head, prev =
null
;
/*CASE 1: the node to delete is the head of the list update the pointer.*/
if
(currNode !=
null
&& currNode.data == key) {
list.head = currNode.next;
// update the pointer to the head
// Return the updated List
return
list;
}
/*CASE 2: the element is womewhere else*/
// I am looking for the data to delete, // keeping track of the previous node // and when necessary, change currNode.next
while
(currNode !=
null
&& currNode.data != key) {
// if currNode does not contain the data // move on to the next node
prev = currNode;
currNode = currNode.next;
}
// If the key is present, you should find it in currNode // So currNode should not be null and void
if
(currNode !=
null
) {
// Since the data is contained in currNode // I detach it from the list
prev.next = currNode.next;
}
// CASE 3: the key is not present // If the key is not present, currNode is null
if
(currNode ==
null
) {
System.out.println(key +
" not found"
);
}
// returns the list
return
list;
}
Some deletion variants may result in deletion at the top, deletion in the queue or deletion at a certain position.
Let's see with a drawing.
Conclusions
We have briefly seen how a concatenated list can work. We note that the implementation provided is that of the Java language, but it could easily be converted to other languages that provide adequate mechanisms. Knowing the logic of how these structures work can be very useful when we have to do some rather complicated debugging.
We will see later on an implementation that works the same way, but with different characteristics, since here we take for granted the presence of the null element. We will see an implementation where a specific class will represent the null node.
Java provides specific classes that implement the mechanisms of a concatenated list. We'll see some examples later.
In essence, this is one of those cases where theory comes to our rescue.

Alessio Mungelli
Computer Science student at UniTo (University of Turin), Network specializtion, blogger and writer. I am a kind of expert in Java desktop developement with interests in AI and web developement. Unix lover (but not Windows hater). I am interested in Linux scripting. I am very inquisitive and I love learning new stuffs.
Related Posts
Node.js and npm: introductory tutorial
In this tutorial we will see how to install and use both Node.js and the npm package manager. In addition, we will also create a small sample application. If you…
How to connect to MySQL with Node.js
Let's see how you can connect to a MySQL database using Node.js, the popular JavaScript runtime environment. Before we start, it is important to note that you must have Node.js installed…
JavaScript Programming Styles: Best Practices
When programming with JavaScript there are certain conventions that you should apply, especially when working in a team environment. In fact, it is common to have meetings to discuss standards…
Secret iPhone codes to unlock hidden features
We love that our devices have hidden features. It's fun to learn something new about the technology we use every day, to discover those little features that aren't advertised by the…
Difference between arrow and normal functions in JavaScript
In this tutorial we are going to see how arrow functions differ from normal JavaScript functions. We will also see when you should use one and when you should use…
JavaScript Arrow functions: What they are and how to use them
In this article we are going to see what they are and how to use JavaScript Arrow Functions, a new feature introduced with the ES6 standard (ECMAScript 6). What are Arrow…
How to insert an element into an array with JavaScript
In this brief tutorial you will learn how to insert one or more elements into an array with JavaScript. For this we will use the splice function. The splice function will not…
What is the difference between primitives types and objects in JavaScript?
In this short tutorial we are going to look at the differences between primitive types and objects in JavaScript. To start with, we're going to look at what primitive types…
How to get DOM elements with JavaScript
When you access any element of the DOM, it is usual to save it in a variable. This is something that at first might seem very simple, but if you…
How to reverse an array in JavaScript
In this tutorial we are going to see how you can change the order of the elements of an array so that they are inverted. You could use a loop…
How synchronize the scroll of two divs with JavaScript
In case you have two divs of different sizes you may sometimes want to scroll both at the same time but at different speeds depending on their size. For example,…
How to use the codePointAt method in JavaScript
The JavaScript codePointAt method has more or less the same function as the charCodeAt method, used to get the 16-bit Unicode representation of the character at a certain position in…