Linkedlist: структура данных для эффективной работы со списками

Связанный список (linked list)

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

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

// Создаем класс для узла связанного списка
class ListNode {
  int data; // значение узла
  ListNode next; // ссылка на следующий узел
  
  // Конструктор для инициализации узла
  ListNode(int data) {
    this.data = data;
    this.next = null;
  }
}

// Создаем класс для связанного списка
class LinkedList {
  ListNode head; // головной узел списка
  
  // Конструктор для инициализации списка
  LinkedList() {
    this.head = null;
  }
  
  // Метод для добавления элемента в конец списка
  public void add(int data) {
    ListNode newNode = new ListNode(data);
    
    if (head == null) {
      head = newNode;
    } else {
      ListNode current = head;
      while (current.next != null) {
        current = current.next;
      }
      current.next = newNode;
    }
  }
  
  // Метод для вывода элементов списка
  public void display() {
    ListNode current = head;
    while (current != null) {
      System.out.print(current.data + " ");
      current = current.next;
    }
    System.out.println();
  }
}

// Пример использования связанного списка
public class Main {
  public static void main(String[] args) {
    LinkedList list = new LinkedList();
    
    list.add(10);
    list.add(20);
    list.add(30);
    
    list.display(); // Выводит: 10 20 30
  }
}

В данном примере мы создаем класс ListNode для представления узла списка. Узел содержит значение data и ссылку next на следующий узел. Затем создаем класс LinkedList, где определяем методы для добавления элемента в конец списка (add) и вывода элементов списка (display). В методе main создаем экземпляр класса LinkedList, добавляем элементы методом add и выводим список методом display.

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