关于链表:数据结构与算法一文搞懂线性表顺序表链表

原创公众号：bigsai 文章珍藏在 GitHub

前言

通过后面数据结构与算法前导我么晓得了数据结构的一些概念和重要性，那么咱们明天总结下线性表相干的内容。当然，我用 本人的了解解 分享给大家。

其实说实话，可能很多人仍然分不清 线性表，程序表，和链表 之间的区别和分割！

• 线性表：逻辑构造，就是对外裸露数据之间的关系，不关怀底层如何实现。
• 程序表、链表：物理构造 ，他是实现一个构造理论物理地址上的构造。比方程序表就是用 数组 实现。而链表用 指针 实现次要工作。不同的构造在不同的场景有不同的区别。

对于 java 来说，大家都晓得 List 接口类型，这就是逻辑构造，因为他就是封装了一个线性关系的一系列办法和数据。而具体的实现其实就是跟物理构造相干的内容。比方程序表的内容存储应用数组的，而后一个 get，set，add 办法都要 基于数组 来实现, 而链表是基于 指针 的。当咱们思考对象中的数据关系就要思考 指针 的属性。指针的指向和 value。

上面用一个图来浅析线性表的关系。可能有些不太确切，然而其中能够参考，并且前面也会依据这个图举例。

线性表根本架构

对于一个 线性表 来说。不论 它的 具体实现 办法如何，咱们应该有的 函数名称 和实现成果 应该统一。你也能够感觉的到在一些构造的设计。比方 List 的 Arraylist 和LinkedList。Map 的 HashMap 和 currentHashMap 他们的接口 api 都是雷同的，然而底层设计实现必定是有区别的。

所以，基于面向对象的编程思维，咱们能够将线性表写成一个接口，而具体实现的程序表和链表能够 继承 这个接口的办法，进步程序的可读性。

还有一点比拟重要的，记得初学数据结构与算法时候实现的线性表都是 固定类型 (int), 随着常识的提高，咱们该当采纳 泛型 来实现更正当。至于接口的具体设计如下：

package LinerList;
public interface ListInterface<T> {void Init(int initsize);// 初始化表
    int length();
    boolean isEmpty();// 是否为空
    int ElemIndex(T t);// 找到编号
    T getElem(int index) throws Exception;// 依据 index 获取数据
    void add(int index,T t) throws Exception;// 依据 index 插入数据
    void delete(int index) throws Exception;
    void add(T t) throws Exception;// 尾部插入
    void set(int index,T t) throws Exception;
    String toString();// 转成 String 输入}

程序表

程序表是基于数组实现的，所以一些办法要基于数组的个性。对于程序表应该有的根底属性为一个 数组 data和一个length.

还有须要留神的是初始化数组的大小，你能够 固定大小 ，然而笔者为了可用性如果内存不够将 扩充二倍 。当然这样很可能因为空间应用问题造成很大的 节约。

一些根本的额办法就不说了，上面着重解说一些初学者容易混同的概念和办法实现。这里把程序表比作 一队坐在板凳上的人。

插入

add(int index,T t)
其中 index 为插入的编号地位，t 为插入的数据



- 依据图片你就很好了解插入操作。当插入一个 index 时候，他的前面所有元素都要后移一位。你能够看的出插入时候整个操作的臃肿性。所以这也是程序表 性能体现最差 的中央, 频繁的插入，删除。

删除

同理，删除也是十分占用资源的。原理和插入相似，不过人走了，空一个小板凳 前面的人须要 往前挪。

其余操作

其余操作就很简略了。比方如果依照编号获取数据 getElem(int index)，你能够间接依据数据坐标返回。a[index]，而其余操作，能够通过遍历间接 操作数组 即可。

链表

我想，表应该是很多人感觉很绕的货色，这个很大起因可能因为 指针 。很多人说java 没指针，其实 java 他也有隐形指针。只不过不能间接用罢了。

指针建设的数据关系往往比数组这些要形象的多。对于指针域，你把他当成一个对象就好了，不过这个对象指向的是 另一个同等级对象 。对于这个关系，你能够比作每个 person 类。每个 person 类都有 老公 (老婆), 而这个老公老婆也是一个理论对象，能够了解这更像一种 逻辑约定关系 ，而不是硬生生的关系吧。
指针你能够思考成 脑子记忆 。下面的程序表咱们说它 有序 因为每个 小板凳 (数组) 有编号 ，咱们能够依据这个来确定地位。而对于 链表来说，你能够看作成一个站在操场上的一队人。而他的操作也略有不同，上面针对一些比拟非凡和重要的进行演绎。

根本构造

对于线性表，咱们只须要一个 data 数组和 length 就能示意根本信息。而对于链表，咱们须要一个node(head 头节点)，和length, 当然，这个 node 也是一个构造体。

class node<T>{
    T data;// 节点的后果
    node next;// 下一个连贯的节点
    public node(){}
    public node(T data)
    {this.data=data;}
    public node(T data, node next) {
        this.data = data;
        this.next = next;
    } 
}

当然，这个节点有 数据域 和指针域。数据域就是寄存实在的数据，而指针域就是寄存下一个 node 的指针。所以相比程序表，如果用满数组状况下，链表占用更多的资源，因为它要寄存指针占用资源。

插入

add(int index,T t)
其中 index 为插入的编号地位，t 为插入的数据
退出插入一个节点node，依据 index 找到插入的前一个节点叫pre。那么操作流程为

1. node.next=pre.next如下 1 的操作，将插入节点前面分割起来。此时 node.next 和 pre.next 统一。
2. pre.next=node因为咱们要插入 node，而 node 链能够代替 pre 本身的 next。那么间接将 pre 指向 node。那么就相当于原始链表插入了一个 node。

带头节点与不带头节点

很多人搞不清什么是 带头节点 和不带头节点 。带头节点就是 head 节点不放数据，第 0 项从 head 前面那个开始数。而不带头节点的链表head 放数据，head 节点就是 第 0 位 。
次要区别：

• 带头节点和不带头节点的次要区别就在 插入删除首位 ，尤其是首位插入。带头节点找元素须要多遍历一次因为它的第一个 head 节点是头节点，不存数据( 可看作一列火车的火车头 )。而不便的就是 带头节点在首位插入更简略 。因为插入 第 0 位 也是在head 的前面。
• 而不带头节点的链表就须要非凡思考首位。因为插入第 0 位其实是插入 head 的后面。假如有 head，插入 node。具体操作为：

1. node.next=head；(node 指向 head，node 这条链成咱们想要的链)
2. head=node；(很多人想不明确，其实这个时候 node 才是 插入后最长链的 首位节点 ，head 在他的前面，而在链表中head 通常示意首位节点，所以 head 不示意第二个节点， 间接 "="node 节点。这样 head 和 node 都示意操作实现的链表。然而对外裸露的只有 head。所以 head 只能指向第一个节点！)

插入尾

• 而在插入尾部的时候，须要留神尾部的 next 为null。不能和插入一般地位相比！

删除

依照 index 移除：delete(int index)

• 找到该 index 的节点 node。node.next=node.next.nex

依照尾部移除(拓展)：deleteEnd()
这个办法我没有写，然而我给大家讲一下，依照尾部删除的思维就是：

1. 申明一个 node 为 head。
2. 当 node.next！=null 时node=node.next 指向下一个
3. 当 node.next==null 时候。阐明这个节点时最初一个。你能够node=null。这个这个 node 的前驱 pre 的 next 就是 null。这个节点就被删除了。

头部删除(带头节点)：

• 带头节点的删除和一般删除始终。间接head.next(第 1 个元素)=head.next.next(第二个元素)
• 这样 head.next 就间接指向第二个元素了。第一个就被删除了

头部删除(不带头节点)

• 咱们晓得不带头节点的 第一个 就是 存货真价实的元素 的。不带头节点删除也很简略。间接 将 head 移到第二位 就行了。即：head=head.next

其余

• 对于其余操作，次要时联合查找。而单链表的查找时 从 head 开始 。而后另一个节点team=head 或head.next。而后用这个节点不停的等于它指向的 next 去查找咱们须要的内容即 while(循环条件){team=team.next}相似。
• 不同教程和人写的线性表也不统一，这里只给出一个样例学习应用而并不是规范，心愿大家扫视。
• 在实现上用了 带头节点的链表实现，因为比拟方便管理，不须要很多if else.

代码实现

程序表

package LinerList;

public class seqlist<T> implements ListInterface<T> {private Object[] date;// 数组存放数据
    private int lenth;
    public seqlist() {// 初始大小默认为 10
        Init(10);
    }

    public void Init(int initsize) {// 初始化
        this.date=new Object[initsize];
        lenth=0;        
    }
    public int length() {return this.lenth;}

    public boolean isEmpty() {// 是否为空
        if(this.lenth==0)
            return true;
        return false;
    }

    /*
     * * @param t    
     * 返回相等后果，为 - 1 为 false
     */
    public int ElemIndex(T t) {
        // TODO Auto-generated method stub
        for(int i=0;i<date.length;i++)
        {if(date[i].equals(t))
            {return i;}
        }
        return -1;
    }

    /*
     * 取得第几个元素
     */
    public T getElem(int index) throws Exception {
        // TODO Auto-generated method stub
        if(index<0||index>lenth-1)
            throw new Exception("数值越界");
        return (T) date[index];
    }
    
    public void add(T t) throws Exception {// 尾部插入
         add(lenth,t);
    }

    /*
     * 依据编号插入
     */
    public void add(int index, T t) throws Exception {if(index<0||index>lenth)
            throw new Exception("数值越界");
        if (lenth==date.length)// 扩容
        {Object newdate[]= new Object[lenth*2];
            for(int i=0;i<lenth;i++)
            {newdate[i]=date[i];
            }
            date=newdate;
        }
        for(int i=lenth-1;i>=index;i--)// 前面元素后挪动
        {date[i+1]=date[i];
        }
        date[index]=t;// 插入元素
        lenth++;// 程序表长度 +1
        
    }

    public void delete(int index) throws Exception {if(index<0||index>lenth-1)
            throw new Exception("数值越界");
        for(int i=index;i<lenth;i++)//index 之后元素前挪动
        {date[i]=date[i+1];
        }
        lenth--;// 长度 -1    
    }

    @Override
    public void set(int index, T t) throws Exception {if(index<0||index>lenth-1)
            throw new Exception("数值越界");
        date[index]=t;
    }
    public String  toString() {
        String vaString="";
        for(int i=0;i<lenth;i++)
        {vaString+=date[i].toString()+" ";}
        return vaString;
        
    }
}

链表

package LinerList;

class node<T>{
    T data;// 节点的后果
    node next;// 下一个连贯的节点
    public node(){}
    public node(T data)
    {this.data=data;}
    public node(T data, node next) {
        this.data = data;
        this.next = next;
    }
   
}
public class Linkedlist<T> implements ListInterface<T>{

    node head;
    private int length;
    public Linkedlist() {head=new node();
        length=0;
    }
    public void Init(int initsize) {head.next=null;}

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

    
    public boolean isEmpty() {if(length==0)return true;
        else return false;
    }

    /*
     * 获取元素编号
     */
    public int ElemIndex(T t) {
        node team=head.next;
        int index=0;
        while(team.next!=null)
        {if(team.data.equals(t))
            {return index;}
            index++;
            team=team.next;
        }
        return -1;// 如果找不到
    }

    @Override
    public T getElem(int index) throws Exception {
        node team=head.next;
        if(index<0||index>length-1)
        {throw new Exception("数值越界");
        }
        for(int i=0;i<index;i++)
        {team=team.next;}
        return (T) team.data;
    }


    public void add(T t) throws Exception {add(length,t);
        
    }
    // 带头节点的插入，第一个和最初一个一样操作
    public void add(int index, T value) throws Exception {if(index<0||index>length)
        {throw new Exception("数值越界");
        }
        node<T> team=head;//team 找到以后地位 node
        for(int i=0;i<index;i++)
        {team=team.next;}
        node<T>node =new node(value);// 新建一个 node
        node.next=team.next;// 指向 index 前地位的下一个指针
        team.next=node;// 本人变成 index 地位    
        length++;
    }
    

    @Override
    public void delete(int index) throws Exception {if(index<0||index>length-1)
        {throw new Exception("数值越界");
        }
        node<T> team=head;//team 找到以后地位 node
        for(int i=0;i<index;i++)// 标记 team 前一个节点
        {team=team.next;}
        //team.next 节点就是咱们要删除的节点
        team.next=team.next.next;
        length--;
    }

    @Override
    public void set(int index, T t) throws Exception {
        // TODO Auto-generated method stub
        if(index<0||index>length-1)
        {throw new Exception("数值越界");
        }
        node<T> team=head;//team 找到以后地位 node
        for(int i=0;i<index;i++)
        {team=team.next;}
        team.data=t;// 将数值赋值，其余不变
        
    }

    public String toString() {
        String va="";
        node team=head.next;
        while(team!=null)
        {
            va+=team.data+" ";
            team=team.next;
        }
        return va;
    }

}

测试与后果

package LinerList;
public class test {public static void main(String[] args) throws Exception {
        // TODO Auto-generated method stub
        System.out.println("线性表测试：");
        ListInterface<Integer>list=new seqlist<Integer>();
        list.add(5);
        list.add(6);
        list.add(1,8);
        list.add(3,996);
        list.add(7);
        System.out.println(list.ElemIndex(8));
        System.out.println(list.toString());
        list.set(2, 222);
        System.out.println(list.toString());
        list.delete(4);
        System.out.println(list.toString());
        System.out.println(list.length());    
        
        System.out.println("链表测试：");
        list=new Linkedlist<Integer>();
        list.add(5);
        list.add(6);
        list.add(1,8);
        list.add(3,996);
        list.add(7);
        System.out.println(list.ElemIndex(8));
        System.out.println(list.toString());
        list.set(2, 222);
        System.out.println(list.toString());
        list.delete(4);
        System.out.println(list.toString());
        System.out.println(list.length());    
    }
}

输入:

线性表测试：
1
5 8 6 996 7
5 8 222 996 7
5 8 222 996
4
链表测试：
1
5 8 6 996 7
5 222 6 996 7
5 222 6 996
4

总结

这里的只是简略实现，实现根本办法。链表也只是单链表。欠缺水平还能够优化。如果有谬误还请大佬斧正。

单链表 查问速度较慢 ，因为他须要从头遍历。如果频繁操作尾部，能够思考链表中不仅有 head 在加尾tail 节点。而程序表查问速度尽管快然而插入很费时费力。理论利用依据需要抉择！

java 中的 Arraylist 和 LinkedList 就是两种形式的代表，不过 LinkedList 应用双向链表优化，并且 jdk 的 api 做了大量优化。所以大家 不必造轮子 ，能够间接用，然而还是很有 学习价值 的。

如果有不了解或者不懂的能够分割交换探讨。

原创不易，bigsai 请敌人们帮两件事帮忙一下:

1. 点赞、关注反对一下，您的必定是我在思否创作的源源能源。
2. 微信搜寻「bigsai」，关注我的公众号，分享更多内容！

咱们下次再见！