Java linked lists and nodes

Java LinkedList

A Java LinkedList is a linear data structure. As the name suggests, it is a List of data linked with each other. A linked list is a common data structure and has its implementations in almost every language. The idea is the same everywhere with a slight variation of flavor.

Linked List in Java

In Linked List, we are going to defines each nodes with data and a self-referential structure to contain the next node. The first node will be named as head and it will be the access point of the entire list! Therefore, if we need to access any element in the middle or end of the list we shall iterate through the list until we find the required node. In Java, we can use the ready-made class named LinkedList from util package. For instance,

import java.util.*; public class LinkedListDemo < public static void main(String[] args) < List mylist = new LinkedList(); mylist.add(1); mylist.add(2); mylist.add(3); System.out.println(mylist); >> 

OUTPUT

But here we shall learn how to create a LinkedList of our own!

First, we must define a Node. each combination of data and next must be defined in a class called “node”.

This class will have a global variable that will serve as the head node for our List.

public class MyLinkedList < listnode head; //global list head

The basic operations performed on Java LinkedList methods are:

insertion( ) method Java LinkedList

void insertion(int data) < listnode newnode = new listnode(); newnode.data = data; if(head == null) < head = newnode; >else < listnode temp = head; while(temp.next != null) < temp = temp.next; >temp.next = newnode; > >

On line 4, we check if the head value is null? If true, it indicates that it is the first insertion in the list. Therefore, we simply, assign the ‘newnode’ as head for the List.

However, from the 2nd insertion and so on, we iterate to the end of the list by checking for null in the next of current node using ‘if (temp.next == null)’. When reached the end, we link the new node at the tail of the list.

print( ) method in Java LinkedList

Finally, this function is used to print LinkedList in Java. We iterate the end of the list using a similar logic and print the data every time.

deletion( ) method in Java LinkedList

In the deletion function, we get 3 cases:

 void delete(int data) < listnode temp = head; if(temp.data == data) < head = temp.next; return; >while(temp.next != null) < if(temp.next.data == data) < temp.next = temp.next.next; >if(temp.next == null) return; temp = temp.next; > >

For instance, in line 3 we check for the first case, delete the first element. Then in the while block, we search if temp next data matches with the data to be deleted. If true we assign the value of temp.next.next to temp next.

The second if block checking if temp next is null or not, is very important. It is used for the 3rd case, or else a NullPointerException will be thrown.

Java Linked List code example

ListNode

LinkedList

public class MyLinkedList < listnode head; void insertion(int data) < listnode newnode = new listnode(); newnode.data = data; if(head == null) < head = newnode; >else < listnode temp = head; while(temp.next != null) < temp = temp.next; >temp.next = newnode; > > void delete(int data) < listnode temp = head; if(temp.data == data) < head = temp.next; return; >while(temp.next != null) < if(temp.next.data == data) < temp.next = temp.next.next; >if(temp.next == null) return; temp = temp.next; > > void print() < listnode temp = head; System.out.print("my list: "); while(temp != null)< System.out.print(temp.data+" "); temp = temp.next; >System.out.println(); > > 

Driver class

delete the first element in LinkedList java

A Queue is a linear Data structure that follows the FIFO mechanism. First in First out. In other words, it behaves just like a normal queue we see in our day-to-day lives.

To insert a value in the queue, we use the enqueue function. However, it is exactly the same as the insertion function we created for our Linked List.

enqueue( )

We shall insert the queue elements one after the other.

 void enqueue(int data) < listnode newnode = new listnode(); newnode.data = data; if(head == null) < head = newnode; >else < listnode temp = head; while(temp.next != null) < temp = temp.next; >temp.next = newnode; > >

dequeue( )

In this function, we will return the head node and then delete it using the previous delete function.

Driver Code

enqueue and dequeue in java LinkedList

We hope this tutorial helped you to achieve the same. Keep learning keep sharing. Follow us on Facebook and Instagram. Also, if you need any help with Java coding help, feel free to contact us.

Источник

Что «под капотом» у LinkedList?

Как работает ArrayList, вполне понятно. Есть много статей по этому поводу, часть из них иллюстрированы замечательными картинками, так что даже новичкам становится сразу все ясно. К лучшим статьям на эту тему я отношу «Структуры данных в картинках. ArrayList», написанную tarzan82.

Этот же автор описывает принципы работы LinkedList, однако часть данных устарела еще с выходом Java 7, поэтому попытка детально разобраться, что происходит внутри этой коллекции, по рисункам tarzan82 уже сложно. Да и в других источниках я не встретила понятных картинок, потому и возникла идея написать эту статью.

Итак, LinkedList — класс, реализующий два интерфейса — List и Deque. Это обеспечивает возможность создания двунаправленной очереди из любых (в том числе и null) элементов. Каждый объект, помещенный в связанный список, является узлом (нодом). Каждый узел содержит элемент, ссылку на предыдущий и следующий узел. Фактически связанный список состоит из последовательности узлов, каждый из которых предназначен для хранения объекта определенного при создании типа.

Разберемся, что же происходит, когда мы пишем уже простые и привычные строки кода.

1. Создание связанного списка

LinkedList numbers = new LinkedList<>();

Данный код создает объект класса LinkedList и сохраняет его в ссылке numbers. Созданный объект предназначен для хранения целых чисел (Integer). Пока этот объект пуст.

Класс LinkedList содержит три поля:

// модификатор transient указывает на то, что данное свойство класса нельзя // сериализировать transient int size = 0; transient Node first; transient Node last;

2. Добавление объекта в конец связанного списка

Данный код добавляет число 8 в конец ранее созданного списка. Под «капотом» этот метод вызывает ряд других методов, обеспечивающих создание объекта типа Integer, создание нового узла, установку объекта класса Integer в поле item этого узла, добавление узла в конец списка и установку ссылок на соседние узлы.

Для установки ссылок на предыдущий и следующий элементы LinkedList использует объекты своего вложенного класса Node:

private static class Node  < E item; Nodenext; Node prev; Node(Node prev, E element, Node next) < this.item = element; this.next = next; this.prev = prev; >>

При каждом добавлении объекта в список создается один новый узел, а также изменяются значения полей связанного списка (size, first, last).

В случае с добавлением первого элемента создается узел, у которого предыдущий и следующий элементы отсутствуют, т.е. являются null, размер коллекции увеличивается на 1, а созданный узел устанавливается как первый и последний элемент коллекции.

Добавим еще один элемент в нашу коллекцию:

Сначала создается узел для нового элемента (число 5) и устанавливается ссылка на существующий элемент (узел с числом 8) коллекции как на предыдущий, а следующим элементом у созданного узла остается null. Также этот новый узел сохраняется в переменную связанного списка last:

Как можно увидеть на рис. 4, первый элемент коллекции (под индексом 0) пока ссылается на null как на следующий элемент. Теперь эта ссылка заменяется и первый элемент начинает ссылаться на второй элемент коллекции (под индексом 1), а также увеличивается размер коллекции:

3. Добавление объекта в середину связанного списка

LinkedList позволяет добавить элемент в середину списка. Для этого используется метод add(index, element), где index — это место в списке, куда будет вставлен элемент element.

Как и метод add(element), данный метод вызывает несколько других методов. Сначала осуществляется проверка значения index, которое должно быть положительным числом, меньшим или равным размеру списка. Если index не удовлетворит этим условиям, то будет сгенирировано исключение IndexOutOfBoundsException.

Затем, если index равен размеру коллеции, то осуществляются действия, описанные в п. 2, так как фактически необходимо вставить элемент в конец существующего списка.

Если же index не равен size списка, то осуществляется вставка перед элементом, который до этой вставки имеет заданный индекс, т.е. в данном случае перед узлом со значением 5.

Для начала с помощью метода node(index) определяется узел, находящийся в данный момент под индексом, под который нам необходимо вставить новый узел. Поиск данного узла осуществляется с помощью простого цикла for по половине списка (в зависимости от значения индекса — либо с начала до элемента, либо с конца до элемента). Далее создается узел для нового элемента (число 13), ссылка на предыдущий элемент устанавливается на узел, в котором элементом является число 8, а ссылка на следующий элемент устанавливается на узел, в котором элементом является число 5. Ссылки ранее существующих узлов пока не изменены:

Теперь последовательно заменяются ссылки: для элемента, следующего за новым элементом, заменяется ссылка на предыдущий элемент (теперь она указывает на узел со значением 13), для предшествующего новому элементу заменяется ссылка на следующий элемент (теперь она указывает на узел со значением 5). И в последнюю очередь увеличивается размер списка:

4. Удаление объекта из списка

Для удаления одного элемента из списка класс LinkedList предлагает нам аж 10 методов, различающихся по типу возвращаемого значения, наличию или отсутствию выбрасываемых исключений, а также способу указания, какой именно элемент следует удалить:

Рассмотрим удаление элемента из связанного списка по его значению. Удалим элемент со значением 5 из нижепредставленного списка:

numbers.remove(Integer.valueOf(5));

Обратите внимание, что принимаемым значением в методе remove(object) является именно объект, если же мы попытаемся удалить элемент со значением 5 следующей строкой

то получим IndexOutOfBoundsException, т.к. компиллятор воспримет число 5 как индекс и вызовет метод remove(index).

Итак, что же происходит при вызове метода remove(object)? Сначала искомый объект сравнивается по порядку со всеми элементами, сохраненными в узлах списка, начиная с нулевого узла. Когда найден узел, элемент которого равен искомому объекту, первым делом элемент сохраняется в отдельной переменной. Потом переопределяются ссылки соседних узлов так, чтобы они указывали друг на друга:

Затем обнуляется значение узла, который содержит удаляемый объект, а также уменьшается размер коллекции:

Теперь вернемся к тому моменту, что элемент из удаляемого узла мы сохраняли в памяти. Зачем мы это делали, спросите вы, если эти данные мы нигде дальше не использовали. Дело в том, что рассматриваемый нами метод в результате своей работу не возвращает удаленный элемент, потому данные, возврещенные вызванным в рамках работы метода unlink(node), вызванного методом remove(object), просто не понадобились. А вот когда мы используем метод remove(index), также вызывающий метод unlink(node), то значение данного элемента последовательно возвращается сначала методом unlink(node), а затем и методом remove(index). Похожая ситуация наблюдается и в остальных методах, возвращающих значение удаленного элемента, только внутри вызываются другие методы, отсоединяющие ссылку: в методах poll(), pollFirst(), remove() и removeFirst() это метод unlinkFirst(node), а в методах pollLast() и removeLast() — метод unlinkLast(node).

Итак, что следует помнить о LinkedList, решая, использовать ли данную коллекцию:

• не синхронизирована;
• позволяет хранить любые объекты, в том числе null и повторяющиеся;
• за константное время O(1) выполняются операции вставки и удаления первого и последнего элемента, операции вставки и удаления элемента из середины списка (не учитывая время поиска позиции элемента, который осуществляется за линейное время);
• за линейное время O(n) выполняются операции поиска элемента по индексу и по значению.

Источник