链表

作者: freemanIT | 来源:发表于2022-03-16 10:44 被阅读0次

链表基础
双向链表&双向循环链表
算法与数据结构:链表
链表
五、双向链表
链表
数据与算法结构
数据结构——链表
链表
Algorithm小白入门 -- 单链表

链表

链表是一种链式存储的线性表, 所有元素的内存地址不一定是连续的

动态数组相比有明显缺点

可能造成内存空间的大量浪费

链表可以做到用多少内存申请多少内存

链表

链表的接口设计

接口设计

设计一个interface list 接口, 抽取相同代码

public interface List<E> {
    
    static final int ELEMENT_NOT_FOUND = -1;
    
    /**
     * 清除元素
     */
    public void clear();
    
    /**
     * 元素的数据
     * @return
     */
    public int size();
    
    /**
     * 是否为空
     * @return 
     */
    public boolean isEmpty();
    
    /**
     * 是否包含某个元素
     * @return n
     */
    public boolean contains(E n);
    
    
    /**
     * 添加元素到尾部
     * @param n
     */
    public void add(E n);
    
    /**
     * 获取index 位置的元素
     * @param index
     * @return
     */
    public E get(int index);
    
    /**
     * index位置插入一个元素
     * @param index
     * @param element
     */
    public E set(int index, E element);
    
    /**
     * index 位置插入一个元素
     * @param index
     * @param element
     * @return
     */
    public void add(int index, E element);
    
    
    /**
     * 删除index 的元素
     * @param index
     * @return
     */
    public E remove(int index);
    
    /**
     * 查看元素的索引
     * @param element
     * @return
     */
    public int indexOf(E element);
}

抽象类实现, 动态数组和链表继承这个抽象类

// 抽象类, 可以部分实现接口的方法, 剩下的交给子类来实现
public abstract class AbstractList<E> implements List<E> {
    
    protected int size;
    
    /**
     * 元素的数据
     * @return
     */
    public int size() {
        return size;
    }
    
    /**
     * 是否为空
     * @return 
     */
    public boolean isEmpty() {
        return size == 0;
    }
    
    /**
     * 是否包含某个元素
     * @return n
     */
    public boolean contains(E element) {
        return indexOf(element) != ELEMENT_NOT_FOUND;
    }
    
    
    /**
     * 添加元素到尾部
     * @param n
     */
    public void add(E element) {
        add(size, element);
    }
    
    /****************封装好的功能函数*******************************/
    // 下标越界抛出的异常
    protected void outOfBounds(int index) {
        throw new IndexOutOfBoundsException("Index:" + index + ", Size:" + size);
    }
    
    // 检查下标越界(不可访问或删除size位置)
    protected void rangeCheck(int index) {
        if (index < 0 || index >= size) {
            outOfBounds(index);
        }
    }
    
    // 检查add()的下标越界(可以在size位置添加)
    protected void rangeCheckForAdd(int index) {
        if (index < 0 || index > size) {
            outOfBounds(index);
        }
    }
}

获取某个位置的元素

    /**
     * 获取index 节点对应的node 对象
     * @param index
     * @return
     */
    private Node<E> node(int index) {
        rangeCheck(index);
        Node<E> node = first;
        for (int i = 0; i < index; i++) {
            node = node.next;
        }
        return node;
    }

清空链表

    public void clear() {
        // 只需要将size 置为0; first 指针置为空, 即可, 指向的链表自动销毁
        size = 0;
        first = null;
    }

添加

单向链表添加

注意边界问题, index 为0, size-1, size

删除

单向链表删除

主要实现

public class LinkedList<E> extends AbstractList<E> {
    
    private Node<E> first;
    
    private static class Node<E> {
        E element;
        Node<E> next;
        public Node(E element, Node<E> next) {
            this.element = element;
            this.next = next;
        }
        
    }

    @Override
    public void clear() {
        // 只需要将size 置为0; first 指针置为空, 即可, 指向的链表自动销毁
        size = 0;
        first = null;
    }

    @Override
    public E get(int index) {
        return node(index).element;
    }

    @Override
    public E set(int index, E element) {
        Node<E> node = node(index);
        E old = node.element;
        node.element = element;
        return old;
    }

    @Override
    public void add(int index, E element) {
        rangeCheckForAdd(index);
        if (index == 0) {
            first = new Node<>(element, first);
        } else {
            // 前一个节点
            Node<E> prev = node(index - 1);
            // 前一个节点的next 为传入的节点, 传入节点的下一个节点为之前的next 节点
            prev.next = new Node<>(element, prev.next);
        }
        // 总数增加
        size++;
    }

    @Override
    public E remove(int index) {
        rangeCheck(index);
        Node<E> node = first;
        if (index == 0) {
            first = first.next;
        } else {
            Node<E> prev = node(index - 1);
            node = prev.next;
            prev.next = node.next;
        }
        size--;
        return node.element;
    }

    @Override
    public int indexOf(E element) {
        if (element == null) {
            Node<E> node = first;
            for (int i = 0; i < size; i++) {
                if (node.element == null) return i;
                node = node.next;
            }
        } else {
            Node<E> node = first;
            for (int i = 0; i < size; i++) {
                if (element.equals(node.element)) return i;
                node = node.next;
            }
        }
        return ELEMENT_NOT_FOUND;
    }
    
    /**
     * 获取index 节点对应的node 对象
     * @param index
     * @return
     */
    private Node<E> node(int index) {
        rangeCheck(index);
        Node<E> node = first;
        for (int i = 0; i < index; i++) {
            node = node.next;
        }
        return node;
    }
    
    @Override
    public String toString() {
        StringBuilder string = new StringBuilder();
        string.append("size=").append(size).append(", [");
        Node<E> node = first;
        for (int i = 0; i < size; i++) {
            if (0 != i) string.append(", ");
            string.append(node.element);
            node = node.next;
        }
        string.append("]");
        
//      // 使用while 方式循环遍历
//      Node<E> node1 = first;
//      while (node1 != null) {
//          node1 = node1.next;
//      }
        
        return string.toString();
    }
}

复杂度分析

动态数组

get 和 set 
最好:O(1)
最坏:O(1)
平均:O(1)
    
add:
最好:O(1), 添加到最后位置
最坏:O(n), 添加到0 位置
平均:O(n)
    
remove:
最好:O(1), 删除最后位置
最坏:O(n), 删除0 位置
平均:O(n)

链表

get 和 set 
最好:O(1), 第0 位置
最坏:O(n), 最后位置
平均:O(n)
    
add:
最好:O(1), 添加到0位置
最坏:O(n), 添加到最后位置
平均:O(n)
    
remove:
最好:O(1), 删除0 位置
最坏:O(n), 删除最后位置
平均:O(n)

复杂度分析

均摊复杂度: 经过连续的多次复杂度比较低的情况, 出现个别副组长的比较高的情况

动态数组的缩容

如果内存使用紧张, 动态数组有比较多的剩余空间, 可以考虑进行缩容操作
比如剩余空间占总容量的一半
如果扩容倍数, 缩容时机不当, 有可能会导致复杂度震荡

双向链表

添加

双向链表添加

    @Override
    public void add(int index, E element) {
        rangeCheckForAdd(index);
        // 末尾添加元素
        if (index == size) {
            Node<E> oldLast = last;
            last = new Node<>(oldLast, element, null);
            if (oldLast == null) {// 在第一个位置添加元素
                first = last;
            } else {
                oldLast.next = last;
            }
        } else {
            Node<E> next = node(index);
            Node<E> prev = next.prev;
            Node<E> node = new Node<>(prev, element, next);
            next.prev = node;
            if (prev == null) {
                first = node;
            } else {
                prev.next = node;
            }
        }
        
        // 总数增加
        size++;
    }

删除

    @Override
    public E remove(int index) {
        rangeCheck(index);
        
        Node<E> node = node(index);
        Node<E> prev = node.prev;
        Node<E> next = node.next;
        
        if (prev == null) {
            first = next;
        } else {
            prev.next = next;
        }
        
        if (next == null) {
            last = prev;
        } else {
            next.prev = prev;
        }
        
        size--;
        return node.element;
    }

注意node的取值方法

    public E get(int index) {
        return node(index).element;
    }

    /**
     * 获取index 节点对应的node 对象
     * @param index
     * @return
     */
    private Node<E> node(int index) {
        rangeCheck(index);
        
        if (index < (size >> 1)) {
            Node<E> node = first;
            for (int i = 0; i < index; i++) {
                node = node.next;
            }
            return node;
        } else {
            Node<E> node = last;
            for (int i = size - 1; i > index; i--) {
                node = node.prev;
            }
            return node;
        }
        
    }

双向链表 VS 单向链表

双向链表和单向链表复杂度对比分析

双向链表 VS 动态数组

动态数组: 开辟和销毁内存空间的次数较少, 但可能造成内存空间的浪费, 可以通过扩容来解决
双向链表: 开辟和销毁内存空间的次数较多, 但不会造成内存控件的浪费

如果频繁在尾部进行添加删除操作, 动态数组, 双向链表均可
如果频繁在头部进行添加删除操作, 建议使用双向链表
在任意位置添加删除, 建议使用双向链表
频繁查询, 随机访问, 建议使用动态数组
单向链表在哈希表中有应用

单向循环链表

添加

单向循环链表添加元素

单个元素

    @Override
    public void add(int index, E element) {
        rangeCheckForAdd(index);
        if (index == 0) {
            Node<E> newFirst = new Node<>(element, first);
            Node<E> last = (size == 0) ? newFirst : node(size - 1);
            last.next = newFirst;
            first = newFirst;
        } else {
            // 前一个节点
            Node<E> prev = node(index - 1);
            // 前一个节点的next 为传入的节点, 传入节点的下一个节点为之前的next 节点
            prev.next = new Node<>(element, prev.next);
        }
        // 总数增加
        size++;
    }

删除

    @Override
    public E remove(int index) {
        rangeCheck(index);
        Node<E> node = first;
        if (index == 0) {
            if (size == 1) {
                first = null;
            } else {
                Node<E> last = node(size - 1);
                first = first.next;
                last.next = first;
            }
        } else {
            Node<E> prev = node(index - 1);
            node = prev.next;
            prev.next = node.next;
        }
        size--;
        return node.element;
    }

双向循环链表

添加

public void add(int index, E element) {
        rangeCheckForAdd(index);
        
        if (index == size) {
            Node<E> oldLast = last;
            last = new Node<>(oldLast, element, first);
            if (oldLast == null) {
                first = last;
                first.next = first;
                first.prev = first;
            } else {
                oldLast.next = last;
                first.prev = last;
            }
        } else {
            Node<E> next = node(index);
            Node<E> prev = next.prev;
            Node<E> node = new Node<>(prev, element, next);
            next.prev = node;
            prev.next = node;
            if (index == 0) { // next == first
                first = node;
            }
        }
        
        // 总数增加
        size++;
    }

删除

public E remove(int index) {
        rangeCheck(index);
        Node<E> node = first;
        if (size == 1) {
            first = null;
            last = null;
        } else {
            node = node(index);
            Node<E> prev = node.prev;
            Node<E> next = node.next;
            prev.next = next;
            next.prev = prev;
            if (node == first) {
                first = next;
            }
            
            if (node == last) {
                last = prev;
            }
        }
        
        size--;
        return node.element;
    }

约瑟夫问题

对原来双向循环链表的修改

    // 增加当前节点
    private Node<E> current;
    // 恢复指向头节点
    public void reset() {
        current = first;
    }
    // 指向下一个节点
    public E next() {
        if (current == null) return null;
        current = current.next;
        return current.element;
    }
    // 修改remove, 删除节点, current 指向下一个节点
    public E remove() {
        if (current == null) return null;
        Node<E> next = current.next;
        E element = remove(current);
        if (size == 0) {
            current = null;
        } else {
            current = next;
        }
        return element;
    }

约瑟夫解法

    void josephus() {
        CircleLinkedList<Integer> list = new CircleLinkedList<>();
        for (int i = 1; i <= 8; i++) {
            list.add(i);
        }
        // current 指向first
        list.reset();
       // 直到空为止
        while (!list.isEmpty()) {
            list.next();
            list.next();
            System.out.println(list.remove());
        }
        
    }

链表基础
链表基础链表长度链表为空链表结构链表增加
双向链表&双向循环链表
链表分为：单链表、单向循环链表、双向链表、双向循环链表本节主要说明：双向链表、双向循环链表定义结点一、双向链表...
算法与数据结构:链表
链表链表还分为单向链表和双向链表, 但是这篇文章只说单向链表 , 下次再讲双向链表 . 链表和数组的区别 ? 链...
链表
链表单链表反转链表中环的检测两个有序链表合并删除链表倒数第n个节点求链表的元素总个数一.单向链表链表共有特征...
五、双向链表
双向链表此前介绍的链表，也叫做单向链表使用双向链表可以提升链表的综合性能修改之前的单链表的源码：双向链表 –...
链表
内容链表数据结构向链表添加元素从链表移除元素使用 LinkedList 表双向链表循环链表链表数据结...
数据与算法结构
线性表顺序表链表（物理上离散，逻辑上连续）链表的类别单链表循环链表双链表链表的操作顺序表与链表的比...
数据结构——链表
本文所讲的链表是单链表，链表采用无头链表科普下：一般链表可以分为有头节点的链表与无头节点的链表有头节点的链表：...
链表
文章结构链表的定义链表的插入和删除操作链表的特性常见的链表结构自定义链表链表的经典操作使用链表实现L...
Algorithm小白入门 -- 单链表
单链表递归反转链表k个一组反转链表回文链表 1. 递归反转链表单链表节点的结构如下： 1.1 递归反转整个单链表...