Как написать свой linkedlist в java

Interview Question: How to implement custom LinkedList in Java?

Hi Guys, This is the first blog in the Data Structure and Problem solving section of my publication. I thought of explaining data structures in a question-answer way. In this blog, step by step we will create our own custom LinkedList in JAVA.

Best Example of LinkedList in Real Life :

As you see in the above picture, Kids holding hands with each other is the best example of LinkedList in practical life. If red shirt and the blue short kid is head then to get the 4th kid with the light blue shirt, you need to iterate from the head to the 4th kid one by one, as a first kid knows the next kid address then next and so on.

As you know, We already have a LinkedList class in java. util package in JDK that has the following methods.

Let’s try to implement these basic functionalities in our Custom LinkedList.

Step 1: We need to create a CustomLinkedList class.

Step 2: Add the Node inner class, in which we have two parameters i.e value and reference to the next node.

Please note, here we are creating a Generic LinkedList. that is why I have added the <E> symbol after the CustomLinkedList.

Interview Tip: generics can be asked by the interviewer frequently.

Giving a brief introduction about generics here by one example.

CustomLinkedList<String> ll = new CustomLinkedList<>();
ll.addAtLast("Ravi");
ll.addAtLast(40); // compilation error

Error:(11, 25) java: incompatible types: int cannot be converted to java.lang.String

Here, the Benefit of generic is that It restricts the user from adding the wrong type in the CustomLinkedList, Type Safty is the benefit of generics.

Step 3: Now, add the head and tail references inside the CustomLinkedList class.

I am tail node just to make the time complexity O(1) while inserting at last of the LinkedList.

Assume, You have not added the tail node, now if you have added 100 elements in your Linked List and now, you want to add 101th element, as you have the head of the linked list, you will iterate till last and then add 101th element. Here time complexity is O(n) which is not good.

Congrats, If you reached this step, as we have completed 50% of the part of the creation of Custom Linked List.

Step 4:

Implement addAtFirst() of the CustomLinkedList. It is quite simple.

Think about it, we have head and tail null at the starting.

1. When we want to add elements at first let’s say 40, we need to create a new node object and now create a link by doing temp. next = head
2. Now the head is pointing to null (40->null), but the head should be pointing to starting of the linked list so, head = temp.

3. Tail should have a reference of the last element if it is null till now, that’s why I wrote: if the tail is null then tail = temp.

Step 4 :

Implement addLast() method for the CustomLinkedList.

Here, when we are adding the first node at the end of the linked list, we need to check if the tail is null or not.

If the tail is null that means it is the first node that you are going to add, so we can call the addAtFirst() method to add the first node. Now, for the next node , we create a node object with the value given and save it as a temp. Now, we can just add created node to the next tail and move the tail to the end by assigning it a temp node.

Voila! We have Just done custom LinkedList implementation in java. Now, See below the full working code of CustomLinkedList with display() method to print complete LinkedList in the console.

Congratulations! If you have read this blog till this point. Then you can create a new functionality easily in Java.

If you have noticed , I didn’t cover remove(Object o) method implemention in this blog . Here is the deal !

This is assignment for you that you have to write the code of remove method for the custom linked list , remove method should remove the first occurrence of object O .

You can comment on this blog ,with your remove method code. I will really appreciate you . If you do this assignment.

Please clap on this blog at least 50 times and follow the “Coding becomes easy” publication for updates regarding upcoming blogs.

Stay Home! Stay Safe! Stay Connected! As covid-19 spreading around the globe.

Name already in use

JBook / collections / list / linked_list.md

• Go to file T
• Go to line L
• Copy path
• Copy permalink

• Open with Desktop
• View raw
• Copy raw contents Copy raw contents

Copy raw contents

Copy raw contents

Класс java.util.LinkedList является второй, после java.util.ArrayList , популярной реализацией интерфейса java.util.List .

Данная реализация основана на двусвязном списке, каждый элемент содержит ссылку на следующий и предыдущий элементы.

Реализация полностю написана на Java и не использует никаких native методов.

Ключевое слово native означает, что метод реализован в платформенно-зависимом коде, чаще всего на C/C++ , и скомпонован в виде динамической библиотеки.

Эта реализация зависит от JVM .

Позволяет хранить любые значения, в том числе и null значения.

Прежде всего обратим внимание на поля класса и выделим наиболее значимые:

В классе java.util.LinkedList объявляется вложенный класс Node .

Класс Node является оберткой, в которую ‘заворачиваются’ все добавляемые элементы, он необходим для того, чтобы объявить ссылки на близлежащие элементы списка.

Представьте себе цепь, каждое звено которой сцеплено с предыдущим и следующим звеном. Так вот каждое звено — это и есть объект класса Node .

Количество элементов в списке хранится в переменной size , точно также как и в java.util.ArrayList .

Класс java.util.LinkedList хранит ссылку на первый и последний элемент списка. Благодрая чему осуществляется быстрая вставка в начало и в конец.

Теперь разберем то, как происходит добавление элементов в список.

В java.util.LinkedList существует несколько методов добавить элемент, для начала разберем наиболее часто используемый.

За добавление элемента в конец у java.util.LinkedList отвечает метод:

Здесь все довольно прозрачно.

Создается объект-обертка Node , туда кладется добавляемый элемент и этот Node становится последним, при этом переопределяются ссылки prev и next . Это выглядит точно также, как если бы к концу цепи добавили еще одно звено: сначала вы это звено создаете, а после скрепляете с конечным элементом.

После добавления возвращается значение true , так как список изменяется — все по контракту Collection#add .

Благодаря тому, что java.util.LinkedList хранит ссылку на последний элемент, добавление в конец происходит за константное время: O(1) .

Точно то же самое происходит при добавлении в начало списка.

А вот добавление в середину выглядит немного иначе.

Добавление в середину

За добавление элемента в конкретную ячейку по индексу у java.util.LinkedList отвечает метод:

Добавление происходит в несколько этапов:

1. Идет проверка на то, что индекс, по которому происходит вставка, не выходит за границы списка:

1. После этого идет проверка на то, что добавление идет в конец или вставка будет где-то в середине. Если вставка будет в конец, то вызыватеся знакомый уже метод linkLast(element) :

1. Если вставка происходит в середину, то вызывается метод node , которому передается индекс элемента, перед которым будет вставляться добавляемый элемент:

1. После того, как найден элемент, перед которым будет вставляен добавляемый элемент, вызывается linkBefore :

Чтобы проще понять то, что происходит снова представьте себе цепь. Вас просят вставить новое звено перед, например, 4-м звеном.

Что вы будете делать?

Сначала найдем место вставки, отсчитав от начала 4 звена, после чего сделаем новое звено и скрепим его в месте цепи, которое только что нашли.

Зеленым отмечен вставляемый элемент.

Начальный список содержит элементы 14, 22 и 16.

Из алгоритма ясно, что раз для нахождения места вставки приходится перебирать список, то вставка элемента по индексу будет происходить за линейное время: O(N) .

Удаление элемента из java.util.LinkedList возможно двумя способами:

• public E remove(int index) — по индексу
• public boolean remove(Object o) — по значению

Удаление по индексу

За удаление по индексу у java.util.LinkedList отвечает метод:

В начале идет привычная проверка на то, не выходит ли индекс за рамки списка.

После этого находится удаляемый элемент с помощью уже знакомого метода node .

Далее, в зависимости от расположения элемента, идет ‘разлинковка’, т.е перебрасывание ссылок.

Красным отмечен удаляемый элемент.

Начальный список содержит элементы 14, 8, 22 и 16.

На рисунке из списка, содержащего значени 14, 8, 22 и 16 удаляется элемент по индексу 1, т.е 8-ка.

В начале этот элемент находится перебором от начала списка, после чего изменяется ссылка next для предыдущего элемента и prev для следующего у найденного для удаления.

У java.util.LinkedList удаление и вставка по логике работы очень похожи.

Удаление по значению

Для удаления по значению у java.util.LinkedList отвечает метод:

Принцип работы абсолютно тот же самый, что и удаления по индексу , изменяется только способ нахождения элемента для удаления.

Список все также обходится начиная с начала, при этом каждый элемент сравнивается с помощью equals .

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

Если же удаялется null значение поиск идет до первого попавшегося null в списке.

После того, как элемент найден, происходит стандартный unlink .

Если в списке присутствуют дубли, то удален будет первый найденный элемент!

Все методы java.util.LinkedList — не синхронизированы.

Поэтому добавление из различных потоков в такой список строго не рекомендуется.

Благодаря тому, что в основе реализации лежит двусвязный список, java.util.LinkedList предоставляет доступ к элементам по индексу и по значению за линейное время: O(N) .

Так как происходит перебор списка!

С другой стороны, благодаря переменным, хранящим начало и конец списка, добавление в начало и в конец происходит за константное время: O(1) .

Так как java.util.LinkedList ‘оборачивает’ добавляемые элементы в Node , то это накладывает дополнительные затраты на хранение списка в памяти.

Реализация java.util.LinkedList из стандартной библиотеки Java предоставляет линейное время доступа к элементам по значению и по индексу.

Однако предоставляет быструю вставку в конец или начало списка.

Данная реализация позволяет хранить любые значения, в том числе дубликаты и null .

Как реализовать класс LinkedList с нуля в Java

Если вы на самом деле строите настоящую производственную систему, то да, вы, как правило, просто используете материал из стандартной библиотеки, если там есть то, что вам нужно. Тем не менее, не думайте об этом как бессмысленное упражнение. Хорошо понимать, как все работает, и understanding linked lists является важным шагом к пониманию более сложных структур данных, многих из которых нет в стандартных библиотеках.

Существуют некоторые различия между тем, как вы создаете связанный список, и тем, как это делает API коллекций Java. API коллекций пытается придерживаться более сложного интерфейса. Ваш LinkedList всегда будет содержать хотя бы один элемент. При такой настройке вы будете использовать null, когда вам нужен пустой список. Думайте о «следующем» как о «остальной части списка». На самом деле многие люди называют это «хвостом» вместо «следующего».

Структуры данных в картинках. LinkedList

Продолжаю начатое, а именно, пытаюсь рассказать (с применением визуальных образов) о том как реализованы некоторые структуры данных в Java.

В прошлый раз мы говорили об ArrayList, сегодня присматриваемся к LinkedList.

LinkedList — реализует интерфейс List. Является представителем двунаправленного списка, где каждый элемент структуры содержит указатели на предыдущий и следующий элементы. Итератор поддерживает обход в обе стороны. Реализует методы получения, удаления и вставки в начало, середину и конец списка. Позволяет добавлять любые элементы в том числе и null.

Создание объекта

Footprint
Object size: 48 bytes

Только что созданный объект list, содержит свойства header и size.

header — псевдо-элемент списка. Его значение всегда равно null, a свойства next и prev всегда указывают на первый и последний элемент списка соответственно. Так как на данный момент список еще пуст, свойства next и prev указывают сами на себя (т.е. на элемент header). Размер списка size равен 0.

Добавление элементов

Footprint
Object size: 112 bytes

Добавление элемента в конец списка с помощью методом add(value), addLast(value)
и добавление в начало списка с помощью addFirst(value) выполняется за время O(1).

Внутри класса LinkedList существует static inner класс Entry, с помощью которого создаются новые элементы.

Каждый раз при добавлении нового элемента, по сути выполняется два шага:

1) создается новый новый экземпляр класса Entry

2) переопределяются указатели на предыдущий и следующий элемент

Добавим еще один элемент

Добавление элементов в «середину» списка

Для того чтобы добавить элемент на определенную позицию в списке, необходимо вызвать метод add(index, value). Отличие от add(value) состоит в определении элемента перед которым будет производиться вставка

Метод entry(index) пробегает по всему списку в поисках элемента с указанным индексом. Направление обхода определяется условием (index < (size >> 1)). По факту получается что для нахождения нужного элемента перебирается не больше половины списка, но с точки зрения асимптотического анализа время на поиск растет линейно — O(n).

Как видно, разработчик может словить IndexOutOfBoundsException, если указанный индекс окажется отрицательным или большим текущего значения size. Это справедливо для всех методов где в параметрах фигурирует индекс.

Удаление элементов

Удалять элементы из списка можно несколькими способами:
— из начала или конца списка с помощью removeFirst(), removeLast() за время O(1);
— по индексу remove(index) и по значению remove(value) за время O(n).

Рассмотрим удаление по значению

Footprint
Object size: 176 bytes

Внутри метода remove(value) просматриваются все элементы списка в поисках нужного. Удален будет лишь первый найденный элемент.

В общем, удаление из списка можно условно разбить на 3 шага:

1) поиск первого элемента с соответствующим значением

2) переопределяются указатели на предыдущий и следующий элемент

3) удаление указателей на другие элементы и предание забвению самого элемента

Итераторы

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

Приведенный выше код поместит указатель в начало списка. Так же можно начать перебор элементов с определенного места, для этого нужно передать индекс в метод listIterator(index). В случае, если необходимо начать обход с конца списка, можно воспользоваться методом descendingIterator().

Стоит помнить, что ListIterator свалится с ConcurrentModificationException, если после создания итератора, список был изменен не через собственные методы итератора.

Ну и на всякий случай примитивный пример перебора элементов:

Итоги

— Из LinkedList можно организовать стэк, очередь, или двойную очередь, со временем доступа O(1);
— На вставку и удаление из середины списка, получение элемента по индексу или значению потребуется линейное время O(n). Однако, на добавление и удаление из середины списка, используя ListIterator.add() и ListIterator.remove(), потребуется O(1);
— Позволяет добавлять любые значения в том числе и null. Для хранения примитивных типов использует соответствующие классы-оберки;
— Не синхронизирован.

Ссылки

Объем занимаемой памяти измерялся с помощью инструмента memory-measurer. Для его использования также понадобится Guava (Google Core Libraries).