【数据结构】线性表：顺序表、单链表、双链表、单循环链表、双循环链表（java实现）

目录

顺序表

单链表

双链表

单循环链表

双循环链表

总结

---

顺序表

package com.list;
import java.lang.*;
import java.util.*;

/**
 * @author PangWanjia
 * @date 2020/11/3 14:50
 */

/*
顺序表和java的ArrayList类
创建顺序表，顺序表的增删查改都是通过下标和容量实现的
*/

class SqListClass<E>{                           //顺序表泛型类
    final int initcapacity=10;					//顺序表的初始容量(常量)
    private E[] data;							//存放顺序表中元素
    private int size;    						//存放顺序表的长度
    private int capacity;    					//存放顺序表的容量
    //构造方法，实现data和size的初始化
    public SqListClass() {
        data = (E[])new Object[initcapacity];	//强制转换为E类型数组
        capacity = initcapacity;
        size=0;
    }
    //容量更新，建了个更大的，把原来的复制过来，更新容量信息
    private void updatecapacity(int newcapacity) {	//改变顺序表的容量为newcapacity
        E[] newdata = (E[])new Object[newcapacity];
        for (int i=0; i<size; i++)					//复制原来的元素
            newdata[i] = data[i];
        capacity = newcapacity;						//设置新容量
        data = newdata;								//仍由data标识数组
    }
    //顺序表创建，从已有数组复制过来，溢出时扩容二倍。
    public void CreateList(E[] a)					//由a整体建立顺序表
    {
        int i;
        for (i=0;i<a.length;i++) {
            if (size==capacity)						//出现上溢出时
                updatecapacity(2*size);	//扩大容量
            data[i]=a[i];
        }
        size=i;										//设置长度
    }
    //添加新元素，先判断是否已满
    public void Add(E e)							//在线性表的末尾添加一个元素e
    {
        if (size==capacity)							//顺序表空间满时倍增容量
            updatecapacity(2*size);
        data[size]=e;
        size++;										//长度增1
    }
    //删除元素
    public void Delete(int i) {						//在线性表中删除序号i位置的元素
        if (i<0 || i>size-1)						//参数错误抛出异常
            throw new IllegalArgumentException("删除:位置i不在有效范围内");
        for (int j=i; j<size-1;j++)					//将data[i]之后的元素前移一个位置
            data[j]=data[j+1];
        size--;										//顺序表长度减1
        if (size>initcapacity && size==capacity/4)		//满足要求容量减半，大于初始容量且是四分之一的时候
            updatecapacity(capacity/2);
    }
    //查找
    public int GetNo(E e){							//查找第一个为e的元素的序号
        int i=0;
        while (i<size && !data[i].equals(e))
            i++;									//查找元素e
        if (i>=size)								//未找到时返回-1
            return -1;
        else
            return i;								//找到后返回其序号
    }
    //插入元素
    public void Insert(int i, E e){				//在线性表中序号i位置插入元素e
        if (i<0 || i>size)							//参数错误抛出异常
            throw new IllegalArgumentException("插入:位置i不在有效范围内");
        if (size==capacity)							//满时倍增容量
            updatecapacity(2*size);
        for (int j=size; j>i; j--)					//将data[i]及后面元素后移一个位置
            data[j]=data[j-1];
        data[i]=e;									//插入元素e
        size++;										//顺序表长度增1
    }
    //打印元素
    public void Print(){
        for(int i = 0;i<size;i++){
            System.out.print(data[i]);
            if(i!=size-1){
                System.out.print(' ');
            }
        }
        System.out.print('\n');
    }
}

public class SqList {
    public static void main(String[] args) {
        Integer [] a = {1,2,3,4,5,6,7};
        System.out.println("创建顺序表：");
        SqListClass<Integer> sq = new SqListClass<Integer>();
        sq.CreateList(a);
        sq.Print();
        //ArrayList类
        System.out.println("通过ArrayList类创建顺序表：");
        ArrayList<Integer> al = new ArrayList<Integer>(Arrays.asList(a));
        System.out.println(al);
    }
}

顺序表，顾名思义按顺序存储数据，可以理解为一些独立的格子，每个格子里的数据并不知道相互之间的关联。

---

单链表

package com.list;

/**
 * @author PangWanjia
 * @date 2020/11/3 16:54
 */

/*
单链表,单链表由数据data和指向下一个元素的指针next组成，主要注意下创建有头插和尾插，以及遍历的方法
*/

//链表结点，包括数据值和下一个结点（相当于用指针指向下一个元素，但是java没有指针）
class LinkNode<E>{
    E data;
    LinkNode<E> next;
    public LinkNode() {							//构造方法
        next=null;
    }
    public LinkNode(E d)						//重载构造方法
    {
        data=d;
        next=null;
    }

}
//链表类
class LinkListClass<E>{
    LinkNode<E> head;//头结点
    public LinkListClass(){
        head = new LinkNode<E>();
    }
    //建立链表：头插法
    public void CreateListF(E[] a){
        for(int i = 0;i<a.length;i++) {
            LinkNode<E> s = new LinkNode<E>(a[i]);
            s.next = head.next;
            head.next = s;
        }
    }
    //建立链表：尾插法
    public void CreateListT(E[] a){
        LinkNode<E> t = new LinkNode<E>();//始终指向最后一个元素
        t = head;
        for(int i = 0;i<a.length;i++) {
            LinkNode<E> s = new LinkNode<E>(a[i]);
            t.next = s;
            t = s;
        }
    }
    //在尾端添加新结点
    public void Add(E e){
        LinkNode<E> s = new LinkNode<E>(e);
        LinkNode<E> p = head;
        while(p.next!=null){
            p = p.next;
        }
        p.next = s;
    }
    //求链表大小
    public int size(){
        int num = 0;
        LinkNode<E> p = head;
        while(p.next!=null){
            p = p.next;
            num++;
        }
        return num;
    }

    //查找指定编号的结点
    public LinkNode<E> Geti(int id){
        if(id<0||id>size()){
            throw new IllegalArgumentException("查找:位置不在有效范围内");
        }
        LinkNode<E> p = head;
        for(int i = 0;i<id;i++){
            p = p.next;
        }
        return p;
    }
    //在指定位置插入结点
    public void Insert(int id,E a){
        if(id<0||id>size()){
            throw new IllegalArgumentException("插入:位置不在有效范围内");
        }
        LinkNode<E> p = new LinkNode<E>(a);
        LinkNode<E> s = Geti(id-1);
        p.next = s.next;
        s.next = p;
    }
    //删除指定位置的元素==========？？？不用释放空间吗？？？
    public void Delete(int id){
        LinkNode<E> s = Geti(id);
        LinkNode<E> p = Geti(id-1);
        p.next = s.next;
    }

    //打印函数，其实就是遍历
    public void Print(){
        LinkNode<E> p = head;
        while(p.next!=null){
            p = p.next;
            System.out.print(p.data+" ");
        }
        System.out.println("");
    }
}

public class LinkList {
    public static void main(String[] args) {
        Integer [] a = {1,2,3,4,5,6,7};
        LinkListClass<Integer> L1 = new LinkListClass<Integer>();
        LinkListClass<Integer> L2 = new LinkListClass<Integer>();
        System.out.println("分别用头插法和尾插法建立链表：");
        L1.CreateListF(a);//头插法建立链表
        L1.Print();
        L2.CreateListT(a);//尾插法建立链表
        L2.Print();
        System.out.println("在指定位置插入结点：");
        L2.Insert(3,30);
        L2.Print();
        System.out.println("删除指定位置的结点：");
        L2.Delete(3);
        L2.Print();
    }
}

单链表，每个结点由数据和next指针组成，next指针指向下一个结点，最后尾结点的next=null。注意下链表的头结点head，我理解是一个用来在该链表开始查询或遍历的记号，头结点是不存储数据的。

与顺序表相比，每个结点都知道自己的下一个结点是谁。

---

双链表

package com.list;

/**
 * @author PangWanjia
 * @date 2020/11/3 21:51
 */

/*
双链表，由数据data、头指针和尾指针组成。
*/

//双链表结点
class DLinkListNode<E>{
    E data;
    DLinkListNode<E> prior;
    DLinkListNode<E> next;
    public DLinkListNode(){
        prior = null;
        next = null;
    }
    public DLinkListNode(E e){
        data = e;
        prior = null;
        next = null;
    }
}
//双链表类
class DLinkListClass<E>{
    DLinkListNode<E> dhead;
    public DLinkListClass(){
        dhead = new DLinkListNode<E>();
        dhead.prior = null;
        dhead.next = null;
    }
    //建立：头插法
    public void CreateListF(E[] a){
        for(int i = 0;i<a.length;i++){
            DLinkListNode<E> s = new DLinkListNode<E>(a[i]);
            s.next = dhead.next;
            if(dhead.next!=null){
                dhead.next.prior = s;
            }
            dhead.next = s;
            s.prior = dhead;
        }
    }
    //建立：尾插法
    public void CreateListR(E[] a){
        DLinkListNode<E> t = dhead;
        for(int i = 0;i<a.length;i++){
            DLinkListNode<E> s = new DLinkListNode<E>(a[i]);
            t.next = s;
            s.prior = t;
            t = s;
        }
    }
    //查找指定索引的结点
    public DLinkListNode<E> Geti(int id){
        DLinkListNode<E> p =  dhead;
        for(int i = 0;i<id;i++){
            p = p.next;
        }
        return p;
    }
    //在尾端添加新结点
    public void Add(E e){
        DLinkListNode<E> p = dhead;
        DLinkListNode<E> s = new DLinkListNode<E>(e);
        while(p.next!=null){
            p = p.next;
        }
        p.next = s;
        s.prior = p;
    }
    //求链表长度
    public int size(){
        int num = 0;
        DLinkListNode<E> p = dhead;
        while(p.next!=null){
            p = p.next;
            num++;
        }
        return num;
    }
    //在指定位置插入结点
    public void Insert(int id,E e){
        DLinkListNode<E> s = new DLinkListNode<E>(e);
        DLinkListNode<E> p = Geti(id-1);
        s.prior = p;
        if(p.next!=null){
            p.next.prior = s;
            s.next = p.next;
        }
        p.next = s;
    }
    //删除指定位置结点
    public void Delete(int id){
        DLinkListNode<E> p = Geti(id);
        p.prior.next = p.next;
        if(p.next!=null){
            p.next.prior = p.prior;
        }

    }
    //打印
    public void Print(){
        DLinkListNode<E> p = dhead;
        while(p.next!=null){
            p = p.next;
            System.out.print(p.data+" ");
        }
        System.out.println();
    }

}

public class DLinkList {
    public static void main(String[] args) {
        Integer [] a = {1,2,3,4,5,6,7};
        System.out.println("头插法建立双链表：");
        DLinkListClass<Integer> L1 = new DLinkListClass<Integer>();
        L1.CreateListF(a);
        L1.Print();
        System.out.println("尾插法建立双链表：");
        DLinkListClass<Integer> L2 = new DLinkListClass<Integer>();
        L2.CreateListR(a);
        L2.Print();
        System.out.println("在尾端增加结点：");
        L2.Add(11);
        L2.Print();
        System.out.println("在指定位置插入结点：");
        L2.Insert(4,30);
        L2.Print();
        System.out.println("删除指定位置的结点：");
        L2.Delete(4);
        L2.Print();
    }
}

双链表，比单链表多了一个prior指针，指向上一个结点。与单链表相比，双链表的结点不仅知道下一个结点，也知道上一个结点。双链表头结点head的prior指针和尾结点的next指针都为null。

---

单循环链表

package com.list;

/**
 * @author PangWanjia
 * @date 2020/11/4 13:56
 */

/*
循环单链表，尾结点的next指针指向头结点head
*/

//结点，跟单链表的一样
class CLinkListClass<E>{
    LinkNode<E> head;
    public CLinkListClass(){
        head=new LinkNode<E>();					//创建头结点
        head.next=head;
    }
    //建立：头插法
    public void CreateListF(E[] a){
        for(int i = 0;i<a.length;i++){
            LinkNode<E> s = new LinkNode<E>(a[i]);
            s.next = head.next;
            head.next = s;
        }
    }
    //建立：尾插法
    public void CreateListR(E[] a){
        LinkNode<E> t = head;
        for (int i = 0;i<a.length;i++){
            LinkNode<E> s = new LinkNode<E>(a[i]);
            s.next = t.next;
            t.next = s;
            t = s;
        }
        t.next = head;
    }
    //在尾端添加新结点
    public void Add(E e){
        LinkNode<E> s = new LinkNode<E>(e);
        LinkNode<E> p = head;
        while(p.next!=head){
            p = p.next;
        }
        p.next = s;
        s.next = head;
    }
    //求链表大小
    public int size(){
        int num = 0;
        LinkNode<E> p = head;
        while(p.next!=head){
            p = p.next;
            num++;
        }
        return num;
    }
    //查找指定编号的结点
    public LinkNode<E> Geti(int id){
        if(id<0||id>size()){
            throw new IllegalArgumentException("查找:位置不在有效范围内");
        }
        LinkNode<E> p = head;
        for(int i = 0;i<id;i++){
            p = p.next;
        }
        return p;
    }
    //在指定位置插入结点
    public void Insert(int id,E a){
        if(id<0||id>size()+1){
            throw new IllegalArgumentException("插入:位置不在有效范围内");
        }
        LinkNode<E> p = new LinkNode<E>(a);
        LinkNode<E> s = Geti(id-1);
        p.next = s.next;
        s.next = p;
    }
    //删除指定位置的元素
    public void Delete(int id){
        LinkNode<E> s = Geti(id);
        LinkNode<E> p = Geti(id-1);
        p.next = s.next;
    }

    //打印
    public void Print(){
        LinkNode<E> p = head;
        while(p.next!=head){
            p = p.next;
            System.out.print(p.data+" ");
        }
        System.out.println("");
    }
}

public class CLinkList {
    public static void main(String[] args) {
        Integer [] a = {1,2,3,4,5,6,7};
        System.out.println("头插法建立循环单链表：");
        CLinkListClass<Integer> L1 = new CLinkListClass<Integer>();
        L1.CreateListF(a);
        L1.Print();
        System.out.println("尾插法建立循环单链表：");
        CLinkListClass<Integer> L2 = new CLinkListClass<Integer>();
        L2.CreateListR(a);
        L2.Print();
        System.out.println("尾部增加结点：");
        L2.Add(11);
        L2.Print();
        System.out.println("指定位置插入结点：");
        L2.Insert(3,30);
        L2.Print();
        System.out.println("删除指定位置结点：");
        L2.Delete(3);
        L2.Print();
    }
}

用与单链表结点相同的结点结构，构建单循环链表，唯一的区别是尾结点的next不再置空了，指向头结点head，即构成一条圈回路。与单链表相比在遍历时是否遍历结束的判断条件不再是是否为null，而是是否为head。

（我这些代码在同一个包下，就直接用了单链表的结点类）

---

双循环链表

package com.list;

/**
 * @author PangWanjia
 * @date 2020/11/4 15:39
 */

/*
双循环链表，结点和双链表一样
*/

class CDLinkListClass<E>{
    DLinkListNode<E> dhead;
    public CDLinkListClass(){
        dhead = new DLinkListNode<E>();
        dhead.next = dhead;
        dhead.prior = dhead;
    }
    //建立：头插法
    public void CreateListF(E[] a){
        for(int i = 0;i<a.length;i++){
            DLinkListNode<E> s = new DLinkListNode<E>(a[i]);
            s.next = dhead.next;
            dhead.next.prior = s;
            dhead.next = s;
            s.prior = dhead;
        }
    }
    //建立：尾插法
    public void CreateListR(E[] a){
        for(int i = 0;i<a.length;i++){
            DLinkListNode<E> s = new DLinkListNode<E>(a[i]);
            s.prior = dhead.prior;
            dhead.prior.next = s;
            dhead.prior = s;
            s.next = dhead;

        }
    }
    //查找指定索引的结点
    public DLinkListNode<E> Geti(int id){
        DLinkListNode<E> p = dhead;
        for(int i = 0;i<id;i++){
            p = p.next;
        }
        return p;
    }
    //在尾端添加新结点
    public void Add(E e){
        DLinkListNode<E> s = new DLinkListNode<E>(e);
        s.prior = dhead.prior;
        dhead.prior.next = s;
        s.next = dhead;
        dhead.prior = s;
    }
    //求链表长度
    public int size(){
        int num = 0;
        DLinkListNode<E> p = dhead;
        while(p.next!=dhead){
            p = p.next;
            num++;
        }
        return num;
    }
    //在指定位置插入结点
    public void Insert(int id,E e){
        DLinkListNode<E> s = new DLinkListNode<E>(e);
        DLinkListNode<E> p = Geti(id-1);
        s.next = p.next;
        p.next.prior = s;
        p.next = s;
        s.prior = p;
    }
    //删除指定位置结点
    public void Delete(int id){
        DLinkListNode<E> p = Geti(id);
        p.prior.next = p.next;
        p.next.prior = p.prior;
    }
    //打印
    public void Print(){
        DLinkListNode<E> p = dhead;
        while(p.next!=dhead){
            p = p.next;
            System.out.print(p.data+" ");
        }
        System.out.println();
    }
}

public class CDLinkList {
    public static void main(String[] args) {
        Integer [] a = {1,2,3,4,5,6,7};
        System.out.println("头插法建立双循环链表：");
        CDLinkListClass<Integer> L1 = new CDLinkListClass<Integer>();
        L1.CreateListF(a);
        L1.Print();
        System.out.println("尾插法建立双循环链表：");
        CDLinkListClass<Integer> L2 = new CDLinkListClass<Integer>();
        L2.CreateListR(a);
        L2.Print();
        System.out.println("在尾端插入结点：");
        L2.Add(11);
        L2.Print();
        System.out.println("在指定位置插入结点：");
        L2.Insert(3,30);
        L2.Print();
        System.out.println("删除指定位置的结点：");
        L2.Delete(3);
        L2.Print();

    }
}

在双链表的基础上，双循环链表尾结点的next指针指向头结点head，头结点head的prior指针指向尾结点，即构成两条圈回路。与双链表相比在遍历时是否遍历结束的判断条件不再是是否为null，而是是否为dhead。

 

总结

基本都是实现了插入（头插和尾插）以及基本的增删查改，有一些涉及传参的其实应该都加上异常判断的，后面有一些没写。

对单链表相当于指向该结点的指针，和该结点指出去的，这两个如何修改，双链表的话是前后共四个指针，基于这些关系基本操作就很容易实现了。

对比下顺序表和链表，顺序表是按序号进行查找，增删的话需要整体移动，链表在查找时需要遍历，增删只需该相关指针即可。所以在查找问题时宜用顺序表，增删问题链表优先。