• 数据结构-链表（java）

    链表

    • 动态数组有个明显的缺点
      • 可能会造成内存空间的大量浪费
    • 能否用到多少就申请多少内存？
      • 链表可以办到这一点
    • 链表是一种链式存储的线性表，所有元素的内存地址不一定是连续的

    image-20220913114940729

    链表的设计

    image-20220913115117671

    接口设计

    • 链表的大部分接口和动态数组是一致的

    image-20220913144101918

    清空元素-clear()

    @Override
public void clear() {
    size=0;
    first=null;
}

    • 1
    • 2
    • 3
    • 4
    • 5

    链表实现

    AbstractList.java

    public abstract class AbstractList<E> implements List<E>  {
	/**
	 * 元素的数量
	 */
	protected int size;
	/**
	 * 元素的数量
	 * @return
	 */
	public int size() {
		return size;
	}

	/**
	 * 是否为空
	 * @return
	 */
	public boolean isEmpty() {
		 return size == 0;
	}

	/**
	 * 是否包含某个元素
	 * @param element
	 * @return
	 */
	public boolean contains(E element) {
		return indexOf(element) != ELEMENT_NOT_FOUND;
	}

	/**
	 * 添加元素到尾部
	 * @param element
	 */
	public void add(E element) {
		add(size, element);
	}
	
	protected void outOfBounds(int index) {
		throw new IndexOutOfBoundsException("Index:" + index + ", Size:" + size);
	}
	
	protected void rangeCheck(int index) {
		if (index < 0 || index >= size) {
			outOfBounds(index);
		}
	}
	
	protected void rangeCheckForAdd(int index) {
		if (index < 0 || index > size) {
			outOfBounds(index);
		}
	}
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55

    LinkedList.java

    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=null;
    }


    @Override
    public boolean contains(E element) {
        return indexOf(element)!=ELEMENT_NOT_FOUND;
    }


    @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);
            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 = prev.next.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位置对应的节点对象
     * @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(i!=0){
                string.append(",");
            }
            string.append(node.element);
            node=node.next;
        }
        string.append("]");
        return string.toString();
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111

    虚拟头节点

    有时候为了让代码更加精简，统一所有节点的处理逻辑，可以在最前面增加一个虚拟的头节点（不存储数据）

    image-20220914091501716

    动态数组、链表复杂度分析

    image-20220914095744872

    双向链表

    image-20220914153715559

    • 使用双向链表可以提升链表的综合性能

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

      • 1
      • 2
      • 3
      • 4
      • 5
      • 6
      • 7
      • 8
      • 9
      • 10
      • 11
      • 12

    • clear()

      @Override
public void clear() {
    size=0;
    first=null;
    last=null;
}

      • 1
      • 2
      • 3
      • 4
      • 5
      • 6

    • add()

      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 = next;
            } else {
                prev.next = next;
            }
        }
    size++;
}

      • 1
      • 2
      • 3
      • 4
      • 5
      • 6
      • 7
      • 8
      • 9
      • 10
      • 11
      • 12
      • 13
      • 14
      • 15
      • 16
      • 17
      • 18
      • 19
      • 20
      • 21
      • 22
      • 23
      • 24

    双向链表VS动态数组

    • 动态数组：开辟、销毁内存空间的次数相对较少，但可能造成内存空间浪费（可通过缩容解决）

    • 双向链表：开辟、销毁内存空间的次数相对较多，但不会造成内存空间的浪费

    • 如果频繁在尾部进行添加、删除操作，动态数组、双向链表均可选择

    • 如果频繁在头部进行添加、删除操作，建议选择使用双向链表

    • 如果有频繁的（在任意位置）添加、删除操作，建议选择使用双向链表

    • 如果有频繁的操作操作（随机访问操作），建议选择使用动态数组

    单向循环链表

    image-20220915134401175

    • add()

      	    @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);
            prev.next = new Node<>(element, prev.next);
        }
        size++;
    }

      • 1
      • 2
      • 3
      • 4
      • 5
      • 6
      • 7
      • 8
      • 9
      • 10
      • 11
      • 12
      • 13
      • 14
      • 15

    • remove()

      @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 = prev.next.next;
    }
    size--;
    return node.element;
}

      • 1
      • 2
      • 3
      • 4
      • 5
      • 6
      • 7
      • 8
      • 9
      • 10
      • 11
      • 12
      • 13
      • 14
      • 15
      • 16
      • 17
      • 18
      • 19
      • 20

    双向循环链表

    image-20220915143039789

    • add()

      	    @Override
    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) {
                    first = next;
                }
            }
        size++;
    }

      • 1
      • 2
      • 3
      • 4
      • 5
      • 6
      • 7
      • 8
      • 9
      • 10
      • 11
      • 12
      • 13
      • 14
      • 15
      • 16
      • 17
      • 18
      • 19
      • 20
      • 21
      • 22
      • 23
      • 24
      • 25
      • 26
      • 27

    • remove()

      	    @Override
    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;
    }

      • 1
      • 2
      • 3
      • 4
      • 5
      • 6
      • 7
      • 8
      • 9
      • 10
      • 11
      • 12
      • 13
      • 14
      • 15
      • 16
      • 17
      • 18
      • 19
      • 20
      • 21
      • 22
      • 23
      • 24

    如何发挥循环链表的最大威力

    • 可以考虑增设1个成员变量、3个方法

    • current：用于指向某个节点

    • void reset()：让current指向头节点first

    • E next()：让current往后走一步，也就是current=current.next

    • E remove()：删除current指向的节点，删除成功后让current指向下一个节点

    • 	    @Override
    public E remove(int index) {
        rangeCheck(index);
        return remove(node(index));
    }
  
    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;
    }
    private E remove(Node<E> node){
        if(size==1){
            first=null;
            last=null;
        }else {
            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;
    }
        public void reset(){
        current=first;
    }
    public E next(){
        if(current==null)return null;
        current=current.next;
        return current.element;
    }

      • 1
      • 2
      • 3
      • 4
      • 5
      • 6
      • 7
      • 8
      • 9
      • 10
      • 11
      • 12
      • 13
      • 14
      • 15
      • 16
      • 17
      • 18
      • 19
      • 20
      • 21
      • 22
      • 23
      • 24
      • 25
      • 26
      • 27
      • 28
      • 29
      • 30
      • 31
      • 32
      • 33
      • 34
      • 35
      • 36
      • 37
      • 38
      • 39
      • 40
      • 41
      • 42
      • 43
      • 44
      • 45

    静态链表

    用数组模拟链表，称为静态链表

    数组的每个元素存放2个数据：值、下个元素的索引

    数据0位置存放的是头节点信息

  • 相关阅读:
    excel高级绘图技巧100讲（六）-甘特图在项目进度上的实战应用案例
    VScode连接远程JupyterNotebook显示点云ply文件
    前缀和与二维前缀和
    我的创作纪念日
    计算机网络：数据报与虚电路
    数据离散化
    【夜读】影响一生的五大定律内心强大的人，有这五种特质
    计算机网络 实验二 交换机的基本配置
    MIPI CSI调试之 raw 数据格式
    小熊听书项目的测试
  • 原文地址：https://blog.csdn.net/weixin_42403632/article/details/126905714