Двусвязный список в Java

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

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

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

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

Разница между DLL и SLL визуализируется на рисунке ниже.

Теперь мы знаем, что узел в двусвязном списке должен содержать три переменные:

Переменная, содержащая фактические данные.

Переменная, хранящая указатель на следующий узел.

Переменная, хранящая указатель на предыдущий узел.

Имея эту информацию в руках, мы можем теперь создать ListNode класс.

package DoublyLinkedList;

/**
 * This class represents a node in a Doubly Linked List.
 * The next-variable is a pointer to the next node,
 * and the prev-variable is a pointer to the previous node.
 * <p>
 *
 * @author Anders Engen Olsen
 * @see DoublyLinkedList
 */

class ListNode<AnyType> {

    // The actual data
    AnyType data;
    // Reference to the next node
    ListNode<AnyType> next;
    // Reference to the prev node
    ListNode<AnyType> prev;

    /**
     * Constructor.
     * Note that the next and prev variables are set to null, thus this is the "root-node"
     *
     * @param data node data
     */
    ListNode(AnyType data) {
        this(null, data, null);
    }

    /**
     * Constructor.
     *
     * @param data node data
     * @param next reference to next node
     * @param prev reference to the previous node
     */
    ListNode(ListNode<AnyType> prev, AnyType data, ListNode<AnyType> next) {
        this.data = data;
        this.next = next;
        this.prev = prev;
    }
}

Хорошо, теперь мы сделали ListNode, который имеет указатель как на предыдущий, так и на следующий узел. Но почему? Каковы преимущества двусвязного списка?

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

Операция удаления намного эффективнее.

Вставка перед узлом также намного эффективнее.

Теперь, как всегда, есть и некоторые недостатки:

Узлы в DLL имеют указатели как на предыдущий, так и на следующий узел. Это требует больше места в памяти.

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

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

addFront: Вставка элемента в начало списка.

addEnd: Вставка элемента в конец списка.

remove: Удаление данного элемента из списка.

addBefore: Вставка перед данным элементом.

addAfter: Вставка после заданного элемента.

isEmpty: Проверка, является ли список пустым.

size: Возвращаясь количество элементов в списке.

Обратите внимание, что в нашем примере не будет дубликатов!

Ниже скелет нашего DoublyLinkedListкласса.

package DoublyLinkedList;

public class DoublyLinkedList<AnyType> {

    // Front / head node
    private ListNode<AnyType> front;

    // Helper, keeping track of size.
    private int size;

    /**
     * Constructing empty list.
     */
    public DoublyLinkedList() {
        front = null;
        size = modificationCount = 0;
    }

    public void addFront(AnyType x) {
    }

    public void addEnd(AnyType x) {

    }

    public void addBefore(AnyType x, AnyType y) {

    }

    public void addAfter(AnyType x, AnyType y) {

    }

    public void remove(AnyType x) {

    }

    public boolean isEmpty() {

    }

    public int size() {

    }
}

Теперь рассмотрим каждый из методов, по одному за раз.

Совет: посмотрите наш обзор лучших онлайн курсов Java!

Начиная с самого простого size(), просто верните переменную размера. Пока вы на это, вы также можете реализовать isEmpty. Верните true, если размер равен 0; в противном случае это неверно.

public boolean isEmpty() {
    return size == 0;
}

public int size() {
    return size;
}

Давайте перейдем к методу addFront. Есть два отдельных сценария, с которыми нам придется иметь дело:

Пустой список: просто инициируйте переднюю переменную как новую ListNode.

Непустой список: сохранить текущий передний узел во временной переменной. Новый front.next будет указывать на предыдущий фронт.

    /**
     * Adding a node to the front of the list.
     *
     * @param x Value to add
     */
    public void addFront(AnyType x) {
        if (isEmpty())
            front = new ListNode<AnyType>(x);
        else {
            ListNode<AnyType> temp = front;
            front = new ListNode<AnyType>(null, x, temp);
            front.next.prev = front;
        }
        size++;
    }

Добавление узла в конец списка несколько похоже. Два сценария одинаковы:

Пустой список: просто инициируйте переднюю переменную как новую ListNode.

Непустой список: пройти список до конца. Сделайте так, чтобы last-node.next указывал на новый узел. Не забудьте обновить предыдущий указатель для вставленного узла!

    /**
     * Inserting a node at the end of the list.
     *
     * @param x Value to add.
     */
    public void addEnd(AnyType x) {
        if (isEmpty())
            front = new ListNode<AnyType>(x);
        else {
            ListNode<AnyType> temp = front;
            // Traverse till end of list
            while (temp.next != null) {
                temp = temp.next;
            }
            temp.next = new ListNode<AnyType>(temp, x, null);
        }
        size++;
    }

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

В противном случае мы создаем новый узел:

Предыдущий новый узел будет current.previous. Следующий новый узел является текущим. Другими словами, мы вставляем между ними.

Если предыдущий узел current не нулевой, мы должны обновить его следующий указатель.

Если current.previous — ноль, мы на фронте. Просто обновите фронт до нового узла.

Наконец, нам нужно обновить current.previous, чтобы указать на новый узел.

    /**
     * Adding node before another node
     *
     * @param x Value to look for, adding before x if found
     * @param y Value to add.
     */
    public void addBefore(AnyType x, AnyType y) {
        // List is empty, can't add
        if (isEmpty())
            throw new NoSuchElementException("Element " + x.toString() + " not found");

        ListNode<AnyType> current = front;

        // Looping through until found
        while (current != null && !current.data.equals(x))
            current = current.next;

        // If null, not found
        if (current == null)
            throw new NoSuchElementException("Element " + x.toString() + " not found");

        ListNode<AnyType> newNode = new ListNode<AnyType>(current.prev, y, current);
        if (current.prev != null)
            current.prev.next = newNode;
        else
            front = newNode;
        current.prev = newNode;

        size++;
    }

Добавление узла за другим очень похоже на добавление ранее.

Создать новый узел. Сделать указатель предыдущего узла указывать на текущий. Следующим указателем для нового узла будет current.next.

Если current.next не равен нулю , мы заставляем current.next.prev указывать на новый узел.

Наконец, мы обновляем current.next, чтобы он указывал на новый узел.

    /**
     * Adding node after another node
     *
     * @param x Value to look for, adding after x if found
     * @param y Value to add.
     */
    public void addAfter(AnyType x, AnyType y) {
        if (isEmpty())
            throw new NoSuchElementException("Element " + x.toString() + " not found");

        ListNode<AnyType> current = front;

        // Looping through until found
        while (current != null && !current.data.equals(x))
            current = current.next;

        // If null, not found
        if (current == null)
            throw new NoSuchElementException("Element " + x.toString() + " not found");

        // Not null, value found
        ListNode<AnyType> newNode = new ListNode<AnyType>(current, y, current.next);
        if (current.next != null)
            current.next.prev = newNode;
        current.next = newNode;

        size++;
    }

Последняя операция, которую мы осуществим . remove

Проверьте, является ли это передним узлом. Если это так, просто сделайте переднюю точку front.next.

Если current.next не равен нулю (то есть не последний узел), то current.next.prev указывает на current.prev.

Сделать current.prev.next указателем на current.next

/**
     * Removing a Node from the list.
     *
     * @param x Value to remove
     */
    public void remove(AnyType x) {
        if (isEmpty())
            throw new NoSuchElementException("Element " + x.toString() + " not found");

        // Removing front element
        if (front.data.equals(x)) {
            front = front.next;
            return;
        }

        ListNode<AnyType> current = front;

        // Looping through until found
        while (current != null && !current.data.equals(x))
            current = current.next;

        // If null, not found
        if (current == null)
            throw new NoSuchElementException("Element " + x.toString() + " not found");

        // It has a next pointer, so not the last node.
        if (current.next != null)
            current.next.prev = current.prev;

        current.prev.next = current.next;

        size--;
    }

Весь полный класс может быть найден ниже, включая тесты JUnit!

package DoublyLinkedList;

/**
 * This class represents a node in a Doubly Linked List.
 * The next-variable is a pointer to the next node,
 * and the prev-variable is a pointer to the previous node.
 * <p>
 *
 * @author Anders Engen Olsen
 * @see DoublyLinkedList
 */

public class ListNode<AnyType> {

    // The actual data
    AnyType data;
    // Reference to the next node
    ListNode<AnyType> next;
    // Reference to the prev node
    ListNode<AnyType> prev;

    /**
     * Constructor.
     * Note that the next and prev variables are set to null, thus this is the "root-node"
     *
     * @param data node data
     */
    ListNode(AnyType data) {
        this(null, data, null);
    }

    /**
     * Constructor.
     *
     * @param data node data
     * @param next reference to next node
     * @param prev reference to the previous node
     */
    ListNode(ListNode<AnyType> prev, AnyType data, ListNode<AnyType> next) {
        this.data = data;
        this.next = next;
        this.prev = prev;
    }
}

package DoublyLinkedList;

import java.util.NoSuchElementException;

public class DoublyLinkedList<AnyType> {

    // Front / head node
    private ListNode<AnyType> front;

    // Helper, keeping track of size.
    private int size;

    /**
     * Constructing empty list.
     */
    public DoublyLinkedList() {
        front = null;
    }

    /**
     * Adding a node to the front of the list.
     *
     * @param x Value to add
     */
    public void addFront(AnyType x) {
        if (isEmpty())
            front = new ListNode<AnyType>(x);
        else {
            ListNode<AnyType> temp = front;
            front = new ListNode<AnyType>(null, x, temp);
            front.next.prev = front;
        }
        size++;
    }

    /**
     * Inserting a node at the end of the list.
     *
     * @param x Value to add.
     */
    public void addEnd(AnyType x) {
        if (isEmpty())
            front = new ListNode<AnyType>(x);
        else {
            ListNode<AnyType> temp = front;
            // Traverse till end of list
            while (temp.next != null) {
                temp = temp.next;
            }
            temp.next = new ListNode<AnyType>(temp, x, null);
        }
        size++;
    }

    /**
     * Adding node before another node
     *
     * @param x Value to look for, adding before x if found
     * @param y Value to add.
     */
    public void addBefore(AnyType x, AnyType y) {
        // List is empty, can't add
        if (isEmpty())
            throw new NoSuchElementException("Element " + x.toString() + " not found");

        ListNode<AnyType> current = front;

        // Looping through until found
        while (current != null && !current.data.equals(x))
            current = current.next;

        // If null, not found
        if (current == null)
            throw new NoSuchElementException("Element " + x.toString() + " not found");

        ListNode<AnyType> newNode = new ListNode<AnyType>(current.prev, y, current);
        if (current.prev != null)
            current.prev.next = newNode;
        else
            front = newNode;
        current.prev = newNode;

        size++;
    }

    /**
     * Adding node after another node
     *
     * @param x Value to look for, adding after x if found
     * @param y Value to add.
     */
    public void addAfter(AnyType x, AnyType y) {
        if (isEmpty())
            throw new NoSuchElementException("Element " + x.toString() + " not found");

        ListNode<AnyType> current = front;

        // Looping through until found
        while (current != null && !current.data.equals(x))
            current = current.next;

        // If null, not found
        if (current == null)
            throw new NoSuchElementException("Element " + x.toString() + " not found");

        // Not null, value found
        ListNode<AnyType> newNode = new ListNode<AnyType>(current, y, current.next);
        if (current.next != null)
            current.next.prev = newNode;
        current.next = newNode;

        size++;
    }

    /**
     * Removing a Node from the list.
     *
     * @param x Value to remove
     */
    public void remove(AnyType x) {
        if (isEmpty())
            throw new NoSuchElementException("Element " + x.toString() + " not found");

        // Removing front element
        if (front.data.equals(x)) {
            front = front.next;
            return;
        }

        ListNode<AnyType> current = front;

        // Looping through until found
        while (current != null && !current.data.equals(x))
            current = current.next;

        // If null, not found
        if (current == null)
            throw new NoSuchElementException("Element " + x.toString() + " not found");

        // It has a next pointer, so not the last node.
        if (current.next != null)
            current.next.prev = current.prev;

        current.prev.next = current.next;

        size--;
    }

    /**
     * @return true if list is empty.
     */
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * @return size of list
     */
    public int size() {
        return size;
    }

    @Override
    public String toString() {
        ListNode<AnyType> temp = front;
        StringBuilder builder = new StringBuilder("[");

        while (temp != null) {
            builder.append(temp.data).append(",");
            temp = temp.next;
        }
        builder.deleteCharAt(builder.length() - 1);
        builder.append("]");
        return builder.toString();
    }
}

import DoublyLinkedList.DoublyLinkedList;
import org.junit.Before;
import org.junit.Test;

import java.util.NoSuchElementException;

import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertTrue;

public class DoublyLinkedListTest {

    private DoublyLinkedList<Integer> list;

    @Before
    public void setUp() {
        list = new DoublyLinkedList<Integer>();
    }

    @Test
    public void testIsEmptyReturnsTrue() {
        assertTrue(list.isEmpty());
    }

    @Test
    public void testIsEmptySizeIsZero() {
        assertEquals(0, list.size());
    }

    @Test(expected = NoSuchElementException.class)
    public void testRemoveNotPresentThrowsException() {
        list.addFront(1);
        list.remove(2);
    }

    @Test(expected = NoSuchElementException.class)
    public void testAddBeforeNotFoundThrowsException() {
        list.addFront(1);
        list.addBefore(0, 2);
    }

    @Test(expected = NoSuchElementException.class)
    public void testAddAfterNotFoundThrowsException() {
        list.addFront(1);
        list.addAfter(0, 2);
    }

    /**
     * Output should be: [4,3,2,1,0]
     */
    @Test
    public void testInsertAtFront() {
        for (int i = 0; i < 5; i++) {
            list.addFront(i);
        }
        assertEquals("[4,3,2,1,0]", list.toString());
    }

    /**
     * Output should be: [0,1,2,3,4]
     */
    @Test
    public void testInsertAtEnd() {
        for (int i = 0; i < 5; i++) {
            list.addEnd(i);
        }
        assertEquals("[0,1,2,3,4]", list.toString());
    }

    /**
     * Output should be: [10,4,3,30,2,1,20,0]
     */
    @Test
    public void testAddBefore() {
        for (int i = 0; i < 5; i++) {
            list.addFront(i);
        }

        list.addBefore(4, 10);
        list.addBefore(0, 20);
        list.addBefore(2, 30);

        assertEquals("[10,4,3,30,2,1,20,0]", list.toString());
    }

    /**
     * Output should be: [0,20,1,2,30,3,4,10]
     */
    @Test
    public void testAddAfter() {
        for (int i = 0; i < 5; i++) {
            list.addEnd(i);
        }

        list.addAfter(4, 10);
        list.addAfter(0, 20);
        list.addAfter(2, 30);

        assertEquals("[0,20,1,2,30,3,4,10]", list.toString());
    }

    /**
     * Output should be: [10,11,12,13,14]
     */
    @Test
    public void testRemove() {
        for (int i = 0; i < 15; i++) {
            list.addEnd(i);
        }

        for (int i = 0; i < 10; i++) {
            list.remove(i);
        }

        assertEquals("[10,11,12,13,14]", list.toString());
    }
}

Двусвязный список в Java

Категории

Последние статьи

Рефакторинг Hudson God Class

Альтернативы синтаксиса Java лямбда

Morphia и MongoDB: развивающиеся структуры документов

OpenShift Express: развертывание приложения Java EE (с поддержкой AS7)

Интеграция jqGrid, REST, AJAX и Spring MVC