Java数据结构之单链表详解

下面是单链表攻略的详细讲解。

什么是单链表？

单链表是一种线性数据结构，它由一系列结点组成，每个结点包含数据域和指针域。数据域用于存储数据，指针域用于指向下一个结点。单链表的优点是插入和删除操作的时间复杂度为O(1)，缺点是随机访问的时间复杂度为O(n)。

单链表的基本操作

单链表的基本操作包括插入操作、删除操作、查找操作和遍历操作。下面将分别介绍这些操作。

插入操作

单链表的插入操作有三种情况：在表头插入、在表尾插入和在指定位置插入。

• 在表头插入：新结点成为头结点，原来的头结点成为新结点的后继结点。

在Java语言中，实现代码如下：

public void addFirst(E e) {
    Node<E> newNode = new Node<>(e);
    newNode.next = head;
    head = newNode;
    size++;
}

• 在表尾插入：新结点成为尾结点，原来的尾结点成为新结点的前驱结点。

在Java语言中，实现代码如下：

public void addLast(E e) {
    Node<E> newNode = new Node<>(e);
    if (size == 0) {
        head = newNode;
    } else {
        Node<E> last = head;
        while (last.next != null) {
            last = last.next;
        }
        last.next = newNode;
    }
    size++;
}

• 在指定位置插入：新结点插入到指定位置，前驱结点指向新结点，新结点指向后继结点。

在Java语言中，实现代码如下：

public void add(int index, E e) {
    if (index < 0 || index > size) {
        throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
    }
    if (index == 0) {
        addFirst(e);
    } else {
        Node<E> prev = head;
        for (int i = 0; i < index - 1; i++) {
            prev = prev.next;
        }
        Node<E> newNode = new Node<>(e);
        newNode.next = prev.next;
        prev.next = newNode;
        size++;
    }
}

删除操作

单链表的删除操作也有三种情况：删除头结点、删除尾结点和删除指定位置。

• 删除头结点：头结点指向后继结点。

在Java语言中，实现代码如下：

public E removeFirst() {
    if (size == 0) {
        throw new NoSuchElementException();
    }
    Node<E> first = head;
    head = first.next;
    size--;
    return first.data;
}

• 删除尾结点：遍历到尾结点的前驱结点，前驱结点的后继结点指向null。

在Java语言中，实现代码如下：

public E removeLast() {
    if (size == 0) {
        throw new NoSuchElementException();
    }
    Node<E> last = head, prev = null;
    while (last.next != null) {
        prev = last;
        last = last.next;
    }
    if (prev == null) {
        head = null;
    } else {
        prev.next = null;
    }
    size--;
    return last.data;
}

• 在指定位置删除：遍历到指定位置的前驱结点，前驱结点的后继结点指向删除结点的后继结点。

在Java语言中，实现代码如下：

public E remove(int index) {
    if (index < 0 || index >= size) {
        throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
    }
    if (index == 0) {
        return removeFirst();
    } else {
        Node<E> prev = head;
        for (int i = 0; i < index - 1; i++) {
            prev = prev.next;
        }
        Node<E> current = prev.next;
        prev.next = current.next;
        size--;
        return current.data;
    }
}

查找操作

单链表的查找操作是指查找某个元素是否在单链表中，如果存在则返回元素的下标，否则返回-1。

在Java语言中，实现代码如下：

public int indexOf(Object o) {
    int index = 0;
    if (o == null) {
        for (Node<E> current = head; current != null; current = current.next) {
            if (current.data == null) {
                return index;
            }
            index++;
        }
    } else {
        for (Node<E> current = head; current != null; current = current.next) {
            if (o.equals(current.data)) {
                return index;
            }
            index++;
        }
    }
    return -1;
}

遍历操作

单链表的遍历操作是指遍历单链表中的所有元素，输出每个元素的值。

在Java语言中，实现代码如下：

public void traverse() {
    for (Node<E> current = head; current != null; current = current.next) {
        System.out.print(current.data + " ");
    }
    System.out.println();
}

示例说明

示例1：在指定位置插入节点

假设有一个单链表，初始状态为：

1->3->5

现在要在第二个结点后面插入一个结点2，操作后单链表变为：

1->3->2->5

Java代码实现如下：

SingleLinkedList<Integer> list = new SingleLinkedList<>();
list.add(0, 1);
list.add(1, 3);
list.add(2, 5);
list.add(2, 2);
list.traverse();

输出结果为：1 3 2 5

示例2：删除指定位置的节点

假设有一个单链表，初始状态为：

1->2->3->4

现在要删除第三个结点，操作后单链表变为：

1->2->4

Java代码实现如下：

SingleLinkedList<Integer> list = new SingleLinkedList<>();
list.add(0, 1);
list.add(1, 2);
list.add(2, 3);
list.add(3, 4);
list.remove(2);
list.traverse();

输出结果为：1 2 4

以上就是单链表详解的攻略，希望对大家有帮助。