[数据结构与算法]单向链表-线性表-数据结构和算法

1 概述

• 链表定义：

  • 链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。

• 链表特点：添加删除快，查找慢

• 链表有很多种不同的类型：单向链表，双向链表以及循环链表。

• 单链表：

  • 单向链表（单链表）是链表的一种，其特点是链表的链接方向是单向的，对链表的访问要通过顺序读取从头部开始；链表是使用指针进行构造的列表；又称为结点列表，因为链表是由一个个结点组装起来的；其中每个结点都有指针成员变量指向列表中的下一个结点；

  • 图示：

2 API

3 初级实现

3.1 源代码及分析

代码如下：

import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.Objects;
import java.util.function.Consumer;

/**
 * @author Administrator
 * @version 1.0
 * @description 单向链表
 * @date 2022-10-08 21:32
 */
public class LinkList<E> {
    /**
     * 节点类
     * @param <E>
     */
    private static class Node<E> {
        E item;
        Node<E> next;
        Node(E item, Node<E> next) {
            this.item = item;
            this.next = next;
        }
    }

    private int size;
    private Node<E> first;
    private Node<E> last;

    public LinkList() {}

    /**
     * 添加元素e
     * @param e     目标元素
     * @return      添加是否成功
     */
    public boolean add(E e) {
        linkLast(e);
        return true;
    }

    /**
     * 插入链表末尾
     * @param e     目标元素
     */
    private void linkLast(E e) {
        Node<E> l = last;
        Node<E> newNode = new Node<>(e, null);
        last = newNode;
        if (l == null) {
            first = newNode;
        } else {
            l.next = newNode;
        }
        size++;
    }

    /**
     * 插入链表末尾
     * @param e     目标元素
     */
    private void linkFirst(E e) {
        Node<E> f = first;
        Node<E> newNode = new Node<>(e, null);
        first = newNode;
        if (f == null) {
            last = newNode;
        } else {
            newNode.next = f;
        }
        size++;
    }

    /**
     * 指定索引位置插入元素
     * @param index     索引
     * @param e         目标元素
     */
    public void add(int index,E e) {
        checkPositionIndex(index);
        if (index == size) {
            linkLast(e);
        } else if (index == 0) {
            linkFirst(e);
        } else {
            linkAfter(e, nodeBefore(index));
        }
    }

    private Node<E> nodeBefore(int index) {
        Node<E> x = first;
        for (int i = 0; i < index - 1; i++) {
            x = x.next;
        }
        return x;
    }

    private void linkAfter(E e, Node<E> before) {
//        assert before != null;
        before.next = new Node<>(e, before.next);
    }

    private Node<E> node(int index) {
        Node<E> x = first;
        for (int i = 0; i < index; i++) {
            x = x.next;
        }
        return x;
    }

    /**
     * 检查位置索引是否合法
     * @param index     目标索引
     */
    private void checkPositionIndex(int index) {
        if (!isPositionIndex(index)) {
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
        }
    }


    /**
     * 检查是否合法的索引
     * @param index     目标索引
     * @return          是否合法
     */
    private boolean isPositionIndex(int index) {
        return index >= 0 && index <= size;
    }

    private String outOfBoundsMsg(int index) {
        return "Index: "+index+", Size: "+size;
    }

    /**
     * 情况链表
     */
    public void clear() {
        for (Node<E> x = first; x != null; ) {
            Node<E> next = x.next;
            x.item = null;
            x.next = null;
            x = next;
        }
        first = last = null;
        size = 0;
    }

    /**
     * 获取指定索引处的元素
     * @param index     目标索引
     * @return          指定索引处的元素
     */
    public E get(int index) {
        checkElementIndex(index);
        return node(index).item;
    }

    private void checkElementIndex(int index) {
        if (!isElementIndex(index)) {
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
        }
    }

    private boolean isElementIndex(int index) {
        return index >= 0 && index < size;
    }

    /**
     * 返回元素在链表中的索引位置
     * @param o     目标元素
     * @return      目标元素在链表中的索引
     */
    public int indexOf(Object o) {
        int index = 0;
        if (o == null) {
            for (Node<E> x = first; x != null; x = x.next) {
                if (x.item == null) {
                    return index;
                }
                index++;
            }
        } else {
            for (Node<E> x = first; x != null; x = x.next) {
                if (o.equals(x.item)) {
                    return index;
                }
                index++;
            }
        }
        return -1;
    }

    /**
     * 移除链表指定索引位置的元素
     * @param index     目标索引
     * @return          目标索引位置的元素值
     */
    public E remove(int index) {
        checkElementIndex(index);
        if (index == 0 || size == 1) {
            return unlinkFirst();
        }
        return unlink(nodeBefore(index));
    }

    private E unlinkFirst() {
        // assert first != null;
        Node<E> f = this.first;
        E item = f.item;
        Node<E> next = this.first.next;
        f.item = null;
        f.next = null;
        first = next;
        if (next == null) {
            last = null;
        }
        size--;
        return item;
    }

    private E unlink(Node<E> prev) {
        // assert prev != null && prev.next != null;
        Node<E> t = prev.next;
        Node<E> next = t.next;
        E item = t.item;
        t.item = null;
        t.next = null;
        prev.next = next;
        if (next == null) {
            last = prev;
        }
        size--;
        return item;
    }

    /**
     * 移除链表中的指定元素
     * @param o     目标元素
     * @return      是否移除成功
     */
    public boolean remove(Object o) {
        Node<E> prev = null;
        if (o == null) {
            for (Node<E> x = first; x != null; x = x.next, prev = x) {
                if (x.item == null) {
                    if (prev == null) {
                        unlinkFirst();
                    } else {
                        unlink(prev);
                    }
                    return true;
                }
            }
        } else {
            for (Node<E> x = first; x != null; x = x.next, prev = x) {
                if (o.equals(x.item)) {
                    if (prev == null) {
                        unlinkFirst();
                    } else {
                        unlink(prev);
                    }
                    return true;
                }
            }
        }
        return false;
    }

    /**
     * 设置指定索引位置元素的值
     * @param index     目标位置索引
     * @param e         要替换的值
     * @return          被替换的旧值
     */
    public E set(int index, E e) {
        checkElementIndex(index);
        Node<E> x = node(index);
        E oldVal = x.item;
        x.item = e;
        return oldVal;
    }

    /**
     * 返回链表的大小
     * @return  链表的大小
     */
    public int size() { return size; }

    public Iterator<E> iterator() {
        return new Itr(0);
    }

    public Iterator<E> listIterator(int index) {
        checkElementIndex(index);
        return new Itr(0);
    }

    @Override
    public String toString() {
        Iterator<E> it = iterator();
        if (! it.hasNext()) {
            return "[]";
        }

        StringBuilder sb = new StringBuilder();
        sb.append('[');
        for (;;) {
            E e = it.next();
            sb.append(e == this ? "(this Collection)" : e);
            if (! it.hasNext()) {
                return sb.append(']').toString();
            }
            sb.append(',').append(' ');
        }
    }

    private class Itr implements Iterator<E> {

        private Node<E> lastReturned;
        private Node<E> next;
        private int nextIndex;

        public Itr(int index) {
            next = node(index);
            nextIndex = index;
        }

        @Override
        public boolean hasNext() {
            return nextIndex < size;
        }

        @Override
        public E next() {
            if (!hasNext()) {
                throw new NoSuchElementException();
            }
            lastReturned = next;
            next = next.next;
            nextIndex++;
            return lastReturned.item;
        }

        @Override
        public void remove() {
            if (lastReturned == null) {
                throw new IllegalStateException();
            }
            Node<E> prev = node(nextIndex - 1);
            if (prev == null) {
                unlinkFirst();
            } else {
                unlink(prev);
            }
            lastReturned = null;
            nextIndex--;
        }

        @Override
        public void forEachRemaining(Consumer<? super E> action) {
            Objects.requireNonNull(action);
            while ( nextIndex < size) {
                action.accept(next.item);
                lastReturned = next;
                next = next.next;
                nextIndex++;
            }
        }
    }
}

• 说明：
  • 此实现为单链表，参考LinkedList源码，LinkedList源码为双向链表，我们放到后面讨论。
  • 我们这里没有做迭代遍历时的同步访问控制，即我们在LinkedList源码看到的modCount检测。
• 代码分析对比：
  • LinkedList源码在unlink移除节点的时候，参数就是目标节点（当前节点），因为它是双向链表，容易获取前驱节点和后继节点；而我们这里是单向链表，所有我们这里移除节点是时候unlinkBefore就传递的是目标节点的前驱节点。
  • LinkedList源码换实现了Deque接口 双向队列和栈相关的代码，我们后面遇到的时候在讲解。

3.2 简单测试

测试代码：

LinkList<Integer> slj = new LinkList<>();
        slj.add(22);
        slj.add(5242);
        slj.add(52);
        System.out.println(slj);
        System.out.println("原数组大小: " + slj.size() );
        System.out.println("====移除索引为0的元素: " + slj.remove(0));
//        System.out.println("====移除索引为1的元素: " + slj.remove(1));
        System.out.println(slj);
        System.out.println("移除后数组大小: " + slj.size());

        Iterator<Integer> iterator = slj.iterator();
        while (iterator.hasNext()) {
            System.out.println(iterator.next());
        }
        
测试结果：
[22, 5242, 52]
原数组大小: 3
====移除索引为0的元素: 22
[5242, 52]
移除后数组大小: 2
5242
52

后记

? 如果小伙伴什么问题或者指教，欢迎交流。

?QQ:806797785

??源代码仓库地址：https://gitee.com/gaogzhen/algorithm

参考：

[1]百度百科.链表[EB/OL].2022-09-17/2022-10-08.

[2]百度百科.单向链表[EB/OL].2022-06-27/2022-10-08.

[3]黑马程序员.黑马程序员Java数据结构与java算法全套教程，数据结构+算法教程全资料发布，包含154张java数据结构图[CP/OL].2020-01-18/2022-10-08.