Структура данных 101: как использовать связанные списки в Java

Хорошее понимание структур данных — важный навык, который должен иметь каждый программист в своем наборе инструментов. Не говоря уже о том, что вопросы, связанные со связанными списками, часто встречаются в большинстве собеседований по кодированию.

Эти навыки демонстрируют вашу способность решать неоднозначные проблемы, комплексно мыслить и выявлять закономерности в коде. Структуры данных используются для организации ваших данных и применения алгоритмов к коду. Платформа Java обеспечивает высокопроизводительные реализации различных структур данных и является одним из наиболее часто тестируемых языков программирования для собеседований.

Сегодня мы рассмотрим одну из самых важных структур данных JavaScript — класс Linked List. Мы посмотрим, как это работает, и узнаем, как мы можем использовать его для хранения данных и управления ими.

Содержание

Что такое связанный список?
Типы связанных списков
Структура односвязного списка
Как создать и использовать связанный список
Добавление элементов в связанный список
Удаление элементов из LinkedList
Обновление элементов в LinkedList
Итерация по LinkedList
Что следует учитывать перед использованием связанного списка
Резюме и ресурсы

Что такое связанный список?

Связанный список — это общая структура данных, состоящая из цепочки узлов. Каждый узел содержит значение и указатель на следующий узел в цепочке.

Указатель заголовка указывает на первый узел, а последний элемент списка указывает на нуль. Когда список пуст, указатель заголовка указывает на нуль.

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

Некоторые важные приложения связанных списков включают:

Реализация HashMaps, файловой системы и списков смежности
Распределение динамической памяти: используйте связанные списки свободных блоков
Выполнение арифметических операций над длинными целыми числами
Ведение каталога имен

Типы связанных списков

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

Есть три разных типа связанных списков, которые служат разным целям для организации нашего кода.

Давайте взглянем.

Односвязный список (однонаправленный)

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

Двунаправленный список (двунаправленный)

Двусвязные списки (DLL) являются расширением базовых связанных списков, но они содержат указатель на следующий узел, а также на предыдущий узел. Это гарантирует, что список можно перемещать в обоих направлениях. Узел DLL состоит из трех основных членов:

Данные
Указатель на следующий узел
Указатель на предыдущий узел

Циклический связанный список

Списки с круговой связью функционируют циклически: первый элемент указывает на последний элемент, а последний элемент указывает на первый. Односвязный список и двусвязный список можно превратить в круговой связанный список. Наиболее важные операции для кругового связного списка:

insert — вставлять элементы в начало списка
display — отобразить список
delete — удалять элементы с начала списка

Структура односвязного списка

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

Связанные списки в Java реализуют интерфейс абстрактного списка и наследуют от него различные конструкторы и методы. Эта последовательная структура данных может использоваться как список, стек или очередь.

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

На следующем рисунке показана теория односвязного списка.

Чтобы реализовать связанный список, нам понадобятся следующие два класса:

Узел класса

Класс Node хранит данные в одном узле. Он может хранить примитивные данные, такие как целые числа и строки, а также сложные объекты, имеющие несколько атрибутов.

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

Вот типичное определение класса Node:

//Class node having Generic data-type <T>

public class Node<T> {

public T data; //Data to store (could be int, string, Object etc)

public Node nextNode; //Pointer to next node in list

}

Связанный список класса

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

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

Односвязный список содержит головной узел: указатель, указывающий на первый элемент списка. Всякий раз, когда мы хотим пройти по списку, мы можем сделать это, используя этот головной узел.

Ниже представлена базовая структура класса односвязного списка:

public class SinglyLinkedList<T> {

    //Node inner class for SLL

    public class Node{

        public T data; //Data to store (could be int, string, Object etc)

        public Node nextNode; //Pointer to next node in list

    }

    public Node headNode; //head node of the linked list

    public int size;      //size of the list

    //constructor

    public SinglyLinkedList() {

        headNode = null;

        size = 0;

    }

}

Как создать и использовать связанный список

Связанные списки довольно просты в использовании, поскольку они имеют линейную структуру. Они очень похожи на массивы, но связанные списки не так статичны, поскольку каждый элемент является отдельным объектом. Вот объявление класса связанного списка Java:

public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, Serializable

Давайте посмотрим на более подробный пример этого в коде. Вот как мы создаем базовый связанный список в Java:

import java.util.LinkedList;

class Main {

  public static void main(String[] args) {

    LinkedList<String> names = new LinkedList<String>();

  }

}

Класс Linked List включен в Java.utilпакет. Чтобы использовать класс, нам нужно импортировать пакет в наш код. Мы инициализировали пустой связанный список с помощью нового ключевого слова. Связанный список может содержать объекты любого типа, в том числе null.

Добавление элементов в связанный список

Чтобы добавить элемент в список, мы можем использовать.add()метод. Этот метод принимает элемент (переданный в качестве аргумента) и добавляет его в конец списка.

import java.util.LinkedList;

class Main {

  public static void main(String[] args) {

    LinkedList<String> names = new LinkedList<String>();

    names.add(«Brian»);

    names.add(«June»);

    System.out.println(names); // This will output [Brian, June]

  }

}

Если вместо этого вы хотите добавить новый элемент в определенное место, вы можете сделать это, передав значение индекса в качестве первого аргумента.add()метода.

names.add(1, «Kathy»);

System.out.println(names);

// Outputs [Brian, Kathy, June]

Вышеупомянутая строка кода вставляет «Кэти» в namesсписок в 1позиции или индексе. Поскольку первый элемент в списке имеет индекс 0, «Кэти» будет вставлена сразу после «Брайан» и непосредственно перед «июнь». Это будет вам знакомо, если вы работали с массивами в JavaScript. Такое поведение возможно, потому что связанные списки индексируются как массивы JavaScript.

Также существуют методы для явного добавления элементов в конец или начало списка.

names.addFirst(«Luke»);

names.addLast(«Harry»);

System.out.println(names);

// Outputs [Luke, Brian, Kathy, June, Harry]

.addFirst()Метод добавляет заданный элемент в начале списка. Чтобы добавить элемент в конечную позицию списка, используйте.addLast()метод. В блоке кода выше «Люк» вставляется в список и становится первым элементом в списке (теперь у него есть индекс 0). В конце вставляется элемент «Гарри», что делает его последним элементом в списке.

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

Подобно добавлению элементов, связанный список предоставляет методы для удаления элементов в списке. Эти методы аналогичны по работе методам добавления элементов в список..remove()Метод удаляет первое вхождение указанного элемента.

names.remove(«Brian»); // This will remove the first occurrence of «Brian» in the LinkedList

Этот метод похож на.add()метод, поскольку он позволяет удалить элемент по определенному индексу. Вызов names.remove(2)удалит элемент по индексу 2, которым в этом списке является «Брайан». Кроме того, можно удалить первый элемент и последний элемент в списке, используя.removeFirst()и.removeLast()методы соответственно.

names.removeFirst();

names.removeLast();

Обновление элементов в LinkedList

Класс Linked List предоставляет метод для изменения элемента в списке. Этот метод вызывается.set(), и он принимает индекс и элемент, который необходимо вставить, заменяя предыдущий элемент в этой позиции.

// names list is: [Kathy, June]

names.set(0, «Katherine»);

// names list is: [Katherine, June]

Итерация по LinkedList

Есть несколько методов для перебора элементов в LinkedList. В приведенном ниже примере мы используем for цикл и.get()метод связанного списка.

for (int i = 0; i < names.size(); i++) {

System.out.println(names.get(i));

}

Мы также могли бы использовать цикл foreach для перебора связного списка.

for (String str : names) {

System.out.println(str);

}

Что следует учитывать перед использованием связанного списка

Связанный список действует как динамический массив. Это означает, что нам не нужно указывать размер при его создании, его размер автоматически изменяется, когда мы добавляем и удаляем элементы. Класс Linked List также реализован с использованием структуры данных двусвязного списка.

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

Такой дизайн делает связанный список полезным в случаях, когда:

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

Этот дизайн также делает LinkedListсравнительно неблагоприятным для ArrayList, который обычно является реализацией List по умолчанию в Java, следующими способами:

Он использует больше памяти, чем ArrayListиз-за хранилища, используемого ссылками на его элементы, один для предыдущего элемента и один для следующего элемента.
Элементы в связанном списке должны читаться в порядке от начала (или до конца), поскольку связанные списки по своей сути являются последовательным доступом.

Резюме и ресурсы

Поздравляем с изучением основ класса связанных списков Java. Выбор использования любой структуры данных, а также любого метода компьютерного программирования должен зависеть от того, какую проблему вы пытаетесь решить.

Чтобы освоить списки понравившихся на Java, нужно еще многое узнать и потренироваться. Вот некоторые из распространенных проблем интервьюирования структур данных для связанных списков: