Операции со связанным списком

декабря 27, 2019

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

Линейно связанные списки

Односвязные списки

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

public class SinglyLinkedList {   

    // Узел односвязного списка    
    class Node { 
        // Данные, которые будут сохранены в узле   
        T data;  
        // Ссылка на следующий узел, 
        // null для последнего узла    
        Node next;   
            
        public Node(T data) {    
            this.data = data;    
            this.next = null;    
        }    
    }    
     
    // Голова односвязного списка 
    // указывает на первый узел в списке; 
    // null для пустого списка
    public Node head = null; 
}

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

Node node = head;
while(node != null) {
    // Делаем что-либо с данными из node.data
    node = node.next;
}

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

public void insertAfter(Node node, Node newNode) {
    newNode.next = node.next
    node.next = newNode
}

Вставка в начале списка требует отдельной функции. Это требует обновления head узла.

public void insertBeginning(Node newNode) {
    // this.head здесь головной узел списка
    newNode.next = this.head 
    this.head = newNode
}

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

// удаляем узел после этого узла
public void removeAfter(Node node) {
    node.next = node.next.next
}

public void removeBeginning() {
    // this.head здесь головной узел списка
    this.head = this.head.next 
}

Обратите внимание, что removeBeginning() устанавливает this.head в null при удалении последнего узла в списке.

Поскольку мы не можем выполнить итерацию в обратном направлении, эффективные операции insertBefore или removeBefore невозможны. Вставка в список перед конкретным узлом требует прохождения по списку, которое в наихудшем случае имеет время выполнения O(n).

Добавление одного связанного списка к другому может быть неэффективным, если ссылка на хвост не сохранена как часть структуры списка, потому что мы должны пройти весь первый список, чтобы найти хвост, а затем добавить второй список к этому. Таким образом, если два линейно связанных списка имеют длину n, добавление в список имеет асимптотическую сложность по времени O(n).

Многие из особых случаев операций со связанным списком могут быть устранены путем включения фиктивного элемента в начале списка. Это гарантирует отсутствие особых случаев для начала списка и делает ненужными как insertBeginning(), так и removeBeginning(). В этом случае первые полезные данные в списке будут найдены по адресу this.head.next.

Круговой связанный список

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

Круговые связанные списки могут быть как одиночными, так и двусвязными.

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

Алгоритмы

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

public void iterate(Node someNode) {
  if (someNode != null){
    Node node = someNode;
    do {
      // делаем что-либо с node.data
      node = node.next
    } while (node != null)
  }
}

Обратите внимание, что тест "while (node != null)" должен находиться в конце цикла. Если тест был перемещен в начало цикла, процедура завершится ошибкой, если в списке будет только один узел.

Следующая функция вставляет узел "newNode" в круговой связанный список после заданного узла "node". Если "node" равен null, предполагается, что список пуст.

public void insertAfter(Node node, Node newNode) {
  if (node == null){
    newNode.next = newNode;
  } else {
    newNode.next = node.next;
    node.next = newNode;
  }
}

Поиск по этому блогу

Alex tools