算法,永远滴神之【链表结构】

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

一、常见数据结构

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

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

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

答：不是，数组是不能变化的，不能扩容，一次性分配，但是线性表可以动态分配，可以扩容，然后其实线性表是一个数据结构抽象，线性表底层可以用数组实现.

file

二、链表

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

2.1 顺序链表

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

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

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

file

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

file

取值：

file

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

总结

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

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 单链表

file

特点

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

插入：需要用末端节点操作，并把上一个节点next的指针指向当前节点

file

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

file file

总结

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

/**
 * <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 双（向）链表

file

特点

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

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

file

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

file
file

总结

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

file

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

/**
 * <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，程序之路，让我们一起探索，共同进步。