关于java:算法永远滴神之链表结构

29次阅读

共计 6918 个字符，预计需要花费 18 分钟才能阅读完成。

这篇文章会让你学到什么？因为数据结构和算法这玩意，不仅自身难度大而且还形象，很多文章说的知识点大都是对的，然而大都过于官网化且不足直观演示，故而不利于咱们了解学习，所以本篇文章不是一个大而全的文章，它只针对常见的一类数据结构进行解释，我会附上相干代码。

一、常见数据结构

1.1 数据结构（分类和概述）

数据结构 分类 概述 特点
数组 非线性构造（程序表） 将具备雷同类型的若干变量有序地组织在一起的汇合 在理论利用中，数组、狭义表、树结构和图构造等数据结构都属于非线性构造。
栈 线性构造 非凡的线性表 先入后出(FILO)
队列 线性构造 非凡的线性表 先入先出(FIFO)
链表 线性构造 程序链表 / 单链表 / 双链表 / 循环链表 不同的表构造，程序表扩容的老本高，插入速度慢，其余的（除循环链表。因为我不是很理解它）跟程序链表的特点相同
树 非线性构造 在树结构中的其余结点都有且仅有一个前驱结点，而且能够有两个后继结点 有父节点，子节点能够有多个
图 非线性构造 在图构造中，数据结点个别称为顶点，而边是顶点的有序偶对。如果两个顶点之间存在一条边，那么就示意这两个顶点具备相邻关系。
堆 非线性构造 树形数据结构 个别探讨的堆都是二叉堆。堆的特点是根结点的值是所有结点中最小的或者最大的，并且根结点的两个子树也是一个堆构造。
散列表 非线性构造 也叫哈希表 依据关键码值 (Key Value) 而间接进行拜访的数据结构

针对数组是否是线性表的争议？

答：不是，数组是不能变动的，不能扩容，一次性调配，然而线性表能够动态分配，能够扩容，而后其实线性表是一个数据结构形象，线性表底层能够用数组实现.

二、链表

链表这里只说程序链表、单（向）链表、双（向）链表

2.1 程序链表

1.java 外面的程序列表，代表为 ArrayList。外面实现是利用（对象）数组实现，扩容是利用算法计算的，如果超出以后数组长度 就会应用新数组，而后把原值针对下标赋值给新数组，最初把指针指向原对象数组。

上面是我手写的一段代码，

程序表插入（add 办法) 须要 计算以后数组是否扩容，如果不须要扩容在 size++ 的下标地位赋值即可，如果须要扩容，原来我是每次扩容 10 次，前面造成如果频繁插入，那扩容的次数就是 (程序链表长度 -10）/10 这样，这样程序链表越长创立新数组的频率就会很高，插入效率就会非常低。前面把 ArrayList 这部分的算法提取进去了。这代表着须要扩容是 在 原数组长度的根底上 +0.5 的原数组长度（即 1.5 倍的扩容）。

删除是如果删除的元素不是最初一位，该元素前面所有想均往前挪一位。

取值：

是否很不便，不须要循环查找。

总结

所以程序链表的的特点是：插入和删除的效率低（扩容老本较大，插入须要可能须要扩容，把新增循环负责，删除经常须要把删除项的前面所有想往前挪一位。），查问效率高（不须要遍历查问), 占用内存随着数据量增大而增大【绝对占用内存比拟多】

import java.util.*;
/**
 *  <li>@author: 程序员 ken </li>
 * <li>Description: 程序表 </li>
 * </ul>
 */
public class MyList<E> {

    private static final int DEFAULT_CAPACITY = 10;

    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    transient Object[] elementData;

    // 数组长度
    private  int size = 0;

    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

    public MyList() {this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;}

    public void add(E e){if(this.elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA){this.elementData = new Object[DEFAULT_CAPACITY];
        }
        // 以后新增 超出元素个数 (须要扩容)
        if(size+1>this.elementData.length){
                    // 超出元素 每次扩容 10
            //Object[] objects = new Object[DEFAULT_CAPACITY + this.elementData.length];

            // 如果没有这个扩容  前面 操作对象的频率就很高 耗费内存就会急剧减少
            int newCapacity  = this.elementData.length + (this.elementData.length >> 1);// 右移一位相当于除以 2

            if(MAX_ARRAY_SIZE < newCapacity){throw new RuntimeException("超出容器最大容量");
            }

            else if(size+1>newCapacity){newCapacity = size+1;}

//            if(MAX_ARRAY_SIZE< DEFAULT_CAPACITY + this.elementData.length){//                throw new RuntimeException("超出容器最大容量");
//            }
//           for (int i = 0; i <this.elementData.length ; i++) {//                objects [i] = this.elementData[i];
//            }
//            this.elementData = objects;

            this.elementData =  Arrays.copyOf(this.elementData, newCapacity);
                        }
                        
        
        }
        this.elementData[size++]=e;
    }

  // 移除数组
    public E remove(int index) {rangeCheck(index);

        //modCount++;
        E oldValue = (E) this.elementData[index];;

        int numMoved = size - index - 1;
        if (numMoved > 0){
                        System.arraycopy(elementData, index+1, elementData, index,
                    numMoved);
                }
            
        elementData[--size] = null; // clear to let GC do its work

        return oldValue;
    }

    public E get(int  index){rangeCheck(index);
        return (E)elementData[index];
    }

    // 范畴查看
    private void rangeCheck(int index) {if (index >= size){throw new IndexOutOfBoundsException(String.format("Index:%s, Size:%s",index,this.size));
        }
    }

    private int size() {return  this.size;}


}

2.1 单链表

特点

有个后置指针指向前面的节点。故只能单向进行查问

插入：须要用末端节点操作，并把上一个节点 next 的指针指向以后节点

删除和取值 都须要遍历（除非是操作首个节点，并且它只用操作后置指针就行了）

总结

所以单（向）链表的的特点是：插入的效率比拟高（但只能单向增加节点），不须要遍历且不须要扩容。删除的效率比程序链表高，因为不须要删除的节点的所有前面节点不须要像程序链表一样往前挪一位。查问效率比拟低（须要遍历查问，且是只能单向遍历，因为不晓得末端节点是“谁”），占用内存较少（因为指针只有一个)



/**
 * <ul>
 * <li>Title: SingleLinkedList</li>
 * <li>Description: 单链表 </li>
 * </ul>
 *
 * @author 程序员 ken
 * @date 2021/5/21 0021 上午 9:59
 */
public class SingleLinkedList<E> {
    transient ListNode<E> first; // 头部节点
    transient ListNode<E> curNode;// 以后操作节点（因为找不到前置节点，所以须要记录前置节点）private  int size;

    // 增加元素
    public void add(E e){final ListNode  node = new ListNode(e,null);
        if(first==null){
            this.first = node ;
            this.curNode = node ;
        }
        else {
            this.curNode.next = node ;
            this.curNode = node ;
        }
        size++;
    }

    // 删除元素
    public boolean remove(int index){if(size<=0 || size < index+1){return false;}
        else{if(index==0){
                this.first = this.size>1?this.first.next:null;
                this.size--;
            }
            ListNode<E> prev = first;
            ListNode<E> ln = first;
            int count =0;
            while (ln.next!=null){
                ln = ln.next;
                count++;
                if(count == index-1){prev = ln;// 记录上一个节点}
                if(count==index){
                    prev.next = ln.next;// 上个节点的下一个节点 等于 删除节点的下一个节点
                    break;
                }
            }
            this.size--;
            return true;
        }
    }


    // 取出元素
    public E get(int index){if (index >= size){throw new IndexOutOfBoundsException(String.format("Index:%s, Size:%s",index,this.size));
        }
        else{if(index==0){return this.first.item;}
            ListNode<E> ln = first;
            int count =0;
            while (ln.next!=null){
                ln = ln.next;
                count++;
                if(count==index){break;}
            }
            return ln.item;
        }
    }

    public int size(){return this.size;}

    // 定义单链表构造
     static class ListNode<E> {
        private E item;
        private ListNode<E> next;

        public ListNode(E item, ListNode<E> next) {
            this.item = item;
            this.next = next;
        }
    }

}

2.1 双（向）链表

特点

有两个指针，别离指向上一个节点和下一个节点。（所以既能向前操作 又能向后操作）

插入：分两种状况 1. 插入在后面，须要把下一个节点的前置节点指向它 2. 插入在前面，须要把上一个节点的后置节点指向它
（这些都是绝对，如果没有元素，操作的都是第一个节点）

删除和取值 都须要遍历，且删除元素 须要同时操作元素的前置节点 和后置节点的后 前 指向（前置节点的后置节点 等于以后节点的后置节点，前置节点的后置节点 等于以后节点的后置节点）


总结

所以双（向）链表的的特点是：插入的效率比拟高（既能够向前插入 也能够向后插入，比单链表灵便），不须要遍历且不须要扩容。删除的效率比程序链表和单链表高，因为不须要向程序链表一样 删除的节点的所有前面节点不须要像程序链表一样往前挪一位，能够依据下标就近准则 抉择从首节点或尾节点进行查问 删除【这点比单链表灵便】）占用内存较高，因为每个节点都要前置节点和后置节点，链表元素越大，占用内存越高。

（这个是源码外面的，我手写的是从首节点向下寻找删除节点的）



/**
 * <ul>
 * <li>Title: DLinkedList</li>
 * <li>Description: 双向链表 </li>
 * </ul>
 *
 * @author 程序员 ken
 * @date 2021/5/20 22:16
 */
public class DLinkedList<E> {

    private int size = 0;

    transient Node<E> first;

    transient Node<E> last;


   public boolean add(E e) {linkLast(e);
      return true;
    }


    /**
     * Links e as last element.(向后增加元素)
     */
    void linkLast(E e) {
        final Node<E> ln = last;// 记录用于是上一次节点（新增节点）final Node<E> nowNode =new Node<>(last,e,null);
        last = nowNode;
        if(ln==null){first =nowNode;}
        else{ln.next = nowNode;}
        size++;
    }

    /**
     * Links e as first element.(向前增加元素)
     */
    private void linkFirst(E e) {
        final Node<E> f = first;
        final Node<E> newNode = new Node<>(null, e, f);
        first = newNode;
        if (f == null)
            last = newNode;
        else
            f.prev = newNode;
        size++;
    }

    // 删除元素  双链表须要操作前后节点 单链表只须要操作后置节点
    public boolean remove(int index){if(size<=0 || size < index+1){return false;}
        else{Node<E> ln = index==0?first: (index==size-1)?last:null; // 首尾取值优选
            Node<E> next = null;
            Node<E> prev = null;
            if(ln!=null){setLinkedValue(ln);
            }

            int count =0;
            while (ln.next!=null){
                ln = ln.next;
                count++;
                if(count==index){setLinkedValue(ln);
                    break;
                }
            }

            return true;
        }
    }

    /**
     * 性能形容: 设置双链表的值
     * @param ln
     * @return: void 
     * @author: 程序员 ken
     * @date: 2021/5/21 0021 下午 12:50
    */ 
    private void setLinkedValue(Node<E> ln) {
        Node<E> prev;
        Node<E> next;
        prev  = ln.prev;// 以后节点前置节点
        next = ln.next;// 以后节点后置节点
        if(prev!=null){// 阐明是非首节点
            ln.prev.next = next;// 前置节点的后置节点 等于以后节点的后置节点 
        }else{ // 阐明是首节点
            this.first = first.next;
        }
        if(next!=null){ln.next.prev = prev;// 前置节点的后置节点 等于以后节点的后置节点}else{// 阐明是尾结点
            this.last = this.size<=1?this.first:prev;// 后置没有了 阐明要么全副删了 要么只剩一个节点
        }
        this.size--;
    }


    // 取出元素
    public E get(int index){if (index >= size){throw new IndexOutOfBoundsException(String.format("Index:%s, Size:%s",index,this.size));
        }
        else{
            // 首尾取值优选
            if(index==0 || index== this.size-1){return index == this.size-1?this.last.item:this.first.item;}
            Node<E> ln = first;
            int count =0;
            while (ln.next!=null){
                ln = ln.next;
                count++;
                if(count==index){break;}
            }
            return ln.item;
        }
    }

    public int size(){return this.size;}

    static class Node<E>{
        E item;
        Node<E> next;
        Node<E> prev;

        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }

    }

}

三、对于链表的算法题

最初出一个简略算法题，让各位测试一下你们会怎么写？

【题目形容】：

给定两个升序单链表，打印两个升序单链表的公共局部。

输出形容:

第一个链表的长度为 n。
第二个链表的长度为 m。

输入一行整数示意两个升序链表的公共局部的值 (按升序输入)。

示例 1

输出

4

1 2 3 4

5

1 2 3 5 6

输入
1 2 3

下面链表 1 的内容为【1, 2 ,3 ,4】, 链表 1 的内容为【1, 2 , 3 , 5, 6】，记住链表元素是枯燥递增的。公共局部为【1,2,3】

欢送关注我的公众号：程序员 ken，程序之路，让咱们一起摸索，共同进步。

正文完
java
发表至： java
2021-05-23
 0
如何重构
关于java:OpenTelemetry系列-五｜-OpenTelemetry-Java-Instrumentation二次开发指南
关于java:设计模式如何提升-vivo-营销自动化业务扩展性-引擎篇01
Spring-Security-解析五-Spring-Security-Oauth2-开发