《数据结构》线性表——链式存储结构
注意：在java中不存在指针的概念，这里的指针成员实际上存放的是后继结点或者前驱结点的引用！
一、链表的介绍
链表分为两种，一种是单链表，另一个是双链表。
- 单链表：每个结点只设置一个指向其后继结点的指针成员。
- 双链表：每个结点中只设置两个指针成员，分别用于指向其前驱结点和后继结点。
(a)单链表
(b) 双链表
双链表中的头结点不存放任何数据元素（空表是仅包含头结点的链表），存放序号为0的元素的结点称为开始结点或者首结点，存放终端元素的结点称为终端结点或者尾结点。
一般链表的长度不计头结点，仅仅指其中数据结点的个数。
由上图可以看出，其实链表的逻辑结构就像一串珠子，我们可以这么来理解，容易记忆！
图片来源于百度，侵删！
二、构建单链表
1、单链表泛型类：
class LinkNode//单链表结点泛型类{E data;LinkNode next;public LinkNode() {//构造方法next=null;}public LinkNode(E d)//重载构造方法{data=d;next=null;}}public class LinkListClass//单链表泛型类{LinkNode head;//存放头结点public LinkListClass()//构造方法{head=new LinkNode();//创建头结点head.next=null;}private LinkNode geti(int i)//返回序号为i的结点{LinkNode p=head;int j=-1;while (j<i){j++;p=p.next;}return p;}//线性表的基本运算算法}2、头插法建表
public void CreateListF(E[] a)//头插法：由数组a整体建立单链表{LinkNode s;for (int i=0;i<a.length;i++)//循环建立数据结点s{s=new LinkNode(a[i]);//新建存放a[i]元素的结点ss.next=head.next;//将s结点插入到开始结点之前,头结点之后head.next=s;}}3、尾插法建表
public void CreateListR(E[] a)//尾插法：由数组a整体建立单链表{LinkNode s,t;t=head;//t始终指向尾结点,开始时指向头结点for (int i=0;i<a.length;i++) {//循环建立数据结点ss=new LinkNode(a[i]);//新建存放a[i]元素的结点st.next=s;//将s结点插入t结点之后t=s;}t.next=null;//将尾结点的next字段置为null}4、在线性表的末尾添加一个元素e
public void Add(E e)//在线性表的末尾添加一个元素e{LinkNode s=new LinkNode(e);//新建结点sLinkNode p=head;while (p.next!=null)//查找尾结点pp=p.next;p.next=s;//在尾结点之后插入结点s}5、求线性表长度
public int size()//求线性表长度{LinkNode p=head;int cnt=0;while (p.next!=null)//找到尾结点为止{cnt++;p=p.next;}return cnt;}6、设置线性表的长度
public void Setsize(int nlen)//设置线性表的长度{int len=size();if (nlenlen)throw new IllegalArgumentException("设置长度:n不在有效范围内");if (nlen==len) return;LinkNode p=geti(nlen-1);//找到序号为nlen-1的结点pp.next=null;//将结点p置为尾结点}7、返回线性表中序号为i的元素
public E GetElem(int i)//返回线性表中序号为i的元素{int len=size();if (ilen-1)throw new IllegalArgumentException("查找:位置i不在有效范围内");LinkNode p=geti(i);//找到序号为i的结点preturn (E)p.data;}8、设置序号i的元素为e
public void SetElem(int i,E e)//设置序号i的元素为e{if (isize()-1)throw new IllegalArgumentException("设置:位置i不在有效范围内");LinkNode p=geti(i);//找到序号为i的结点pp.data=e;}9、查找第一个为e的元素的序号
public int GetNo(E e)//查找第一个为e的元素的序号{int j=0;LinkNode p=head.next;while (p!=null && !p.data.equals(e)){j++;//查找元素ep=p.next;}if (p==null)//未找到时返回-1return -1;elsereturn j;//找到后返回其序号}10、交换序号i和序号j的元素
public void swap(int i,int j)//交换序号i和序号j的元素{LinkNode p=geti(i);LinkNode q=geti(j);E tmp=p.data;p.data=q.data;q.data=tmp;}11、在线性表中序号i位置插入元素e
public void Insert(int i, E e)//在线性表中序号i位置插入元素e{if (isize())//参数错误抛出异常throw new IllegalArgumentException("插入:位置i不在有效范围内");LinkNode s=new LinkNode(e);//建立新结点sLinkNode p=head=geti(i-1);//找到序号为i-1的结点ps.next=p.next;//在p结点后面插入s结点p.next=s;}12、在线性表中删除序号i位置的元素
public void Delete(int i) //在线性表中删除序号i位置的元素{if (isize()-1)//参数错误抛出异常throw new IllegalArgumentException("删除:位置i不在有效范围内");LinkNode p=geti(i-1);//找到序号为i-1的结点pp.next=p.next.next;//删除p结点的后继结点}13、将线性表转换为字符串
public String toString()//将线性表转换为字符串{String ans="";LinkNode p=head.next;while (p!=null){ans+=p.data+" ";p=p.next;}return ans;}14、单链表完整代码
import java.util.*;@SuppressWarnings("unchecked")class LinkNode//单链表结点泛型类{E data;LinkNode next;public LinkNode() {//构造方法next=null;}public LinkNode(E d)//重载构造方法{data=d;next=null;}}public class LinkListClass//单链表泛型类{LinkNode head;//存放头结点public LinkListClass()//构造方法{head=new LinkNode();//创建头结点head.next=null;}private LinkNode geti(int i)//返回序号为i的结点{LinkNode p=head;int j=-1;while (j<i){j++;p=p.next;}return p;}//线性表的基本运算算法public void CreateListF(E[] a)//头插法：由数组a整体建立单链表{LinkNode s;for (int i=0;i<a.length;i++)//循环建立数据结点s{s=new LinkNode(a[i]);//新建存放a[i]元素的结点ss.next=head.next;//将s结点插入到开始结点之前,头结点之后head.next=s;}}public void CreateListR(E[] a)//尾插法：由数组a整体建立单链表{LinkNode s,t;t=head;//t始终指向尾结点,开始时指向头结点for (int i=0;i<a.length;i++) {//循环建立数据结点ss=new LinkNode(a[i]);//新建存放a[i]元素的结点st.next=s;//将s结点插入t结点之后t=s;}t.next=null;//将尾结点的next字段置为null}public void Add(E e)//在线性表的末尾添加一个元素e{LinkNode s=new LinkNode(e);//新建结点sLinkNode p=head;while (p.next!=null)//查找尾结点pp=p.next;p.next=s;//在尾结点之后插入结点s}public int size()//求线性表长度{LinkNode p=head;int cnt=0;while (p.next!=null)//找到尾结点为止{cnt++;p=p.next;}return cnt;}public void Setsize(int nlen)//设置线性表的长度{int len=size();if (nlenlen)throw new IllegalArgumentException("设置长度:n不在有效范围内");if (nlen==len) return;LinkNode p=geti(nlen-1);//找到序号为nlen-1的结点pp.next=null;//将结点p置为尾结点}public E GetElem(int i)//返回线性表中序号为i的元素{int len=size();if (ilen-1)throw new IllegalArgumentException("查找:位置i不在有效范围内");LinkNode p=geti(i);//找到序号为i的结点preturn (E)p.data;}public void SetElem(int i,E e)//设置序号i的元素为e{if (isize()-1)throw new IllegalArgumentException("设置:位置i不在有效范围内");LinkNode p=geti(i);//找到序号为i的结点pp.data=e;}public int GetNo(E e)//查找第一个为e的元素的序号{int j=0;LinkNode p=head.next;while (p!=null && !p.data.equals(e)){j++;//查找元素ep=p.next;}if (p==null)//未找到时返回-1return -1;elsereturn j;//找到后返回其序号}public void swap(int i,int j)//交换序号i和序号j的元素{LinkNode p=geti(i);LinkNode q=geti(j);E tmp=p.data;p.data=q.data;q.data=tmp;}public void Insert(int i, E e)//在线性表中序号i位置插入元素e{if (isize())//参数错误抛出异常throw new IllegalArgumentException("插入:位置i不在有效范围内");LinkNode s=new LinkNode(e);//建立新结点sLinkNode p=head=geti(i-1);//找到序号为i-1的结点ps.next=p.next;//在p结点后面插入s结点p.next=s;}public void Delete(int i) //在线性表中删除序号i位置的元素{if (isize()-1)//参数错误抛出异常throw new IllegalArgumentException("删除:位置i不在有效范围内");LinkNode p=geti(i-1);//找到序号为i-1的结点pp.next=p.next.next;//删除p结点的后继结点}public String toString()//将线性表转换为字符串{String ans="";LinkNode p=head.next;while (p!=null){ans+=p.data+" ";p=p.next;}return ans;}}三、构建双链表
1、双链表结点泛型类
class DLinkNode//双链表结点泛型类{E data;DLinkNode prior;//前驱结点指针DLinkNode next;//后继结点指针public DLinkNode()//构造方法{prior=null;next=null;}public DLinkNode(E d)//重载构造方法{data=d;prior=null;next=null;}}public class DLinkListClass//双链表泛型类{DLinkNode dhead;//存放头结点public DLinkListClass()//构造方法{dhead=new DLinkNode();//创建头结点dhead.prior=null;dhead.next=null;}private DLinkNode geti(int i)//返回序号为i的结点{DLinkNode p=dhead;int j=-1;while (j<i){j++;p=p.next;}return p;}//线性表的基本运算算法}2、头插法建表
public void CreateListF(E[] a)//头插法：由数组a整体建立双链表{DLinkNode s;for (int i=0;i<a.length;i++)//循环建立数据结点s{s=new DLinkNode(a[i]);//新建存放a[i]元素的结点s，将其插入到表头s.next=dhead.next;//修改s结点的next字段if (dhead.next!=null)//修改头结点的非空后继结点的prior字段dhead.next.prior=s;dhead.next=s;//修改头结点的next字段s.prior=dhead;//修改s结点的prior字段}}3、尾插法建表
public void CreateListR(E[] a)//尾插法：由数组a整体建立双链表{DLinkNode s,t;t=dhead;//t始终指向尾结点,开始时指向头结点for (int i=0;i<a.length;i++)//循环建立数据结点s{s=new DLinkNode(a[i]);//新建存放a[i]元素的结点st.next=s;//将s结点插入t结点之后s.prior=t; t=s;}t.next=null;//将尾结点的next字段置为null}4、在线性表的末尾添加一个元素e
public void Add(E e)//在线性表的末尾添加一个元素e{DLinkNode s=new DLinkNode(e);//新建结点sDLinkNode p=dhead;while (p.next!=null)//查找尾结点pp=p.next;p.next=s;//在尾结点之后插入结点ss.prior=p;}5、求线性表长度
public int size()//求线性表长度{DLinkNode p=dhead;int cnt=0;while (p.next!=null)//找到尾结点为止{cnt++;p=p.next;}return cnt;}6、设置线性表的长度
public void Setsize(int nlen)//设置线性表的长度{int len=size();if (nlenlen)throw new IllegalArgumentException("设置长度:n不在有效范围内");if (nlen==len) return;DLinkNode p=geti(nlen-1);//找到序号为nlen-1的结点pp.next=null;//将结点p置为尾结点}7、返回线性表中序号为i的元素
public E GetElem(int i)//返回线性表中序号为i的元素{int len=size();if (ilen-1)throw new IllegalArgumentException("查找:位置i不在有效范围内");DLinkNode p=geti(i);//找到序号为i的结点preturn (E)p.data;}8、设置序号i的元素为e
public void SetElem(int i,E e)//设置序号i的元素为e{if (isize()-1)throw new IllegalArgumentException("设置:位置i不在有效范围内");DLinkNode p=geti(i);//找到序号为i的结点pp.data=e;}9、查找第一个为e的元素的序号
public int GetNo(E e)//查找第一个为e的元素的序号{int j=0;DLinkNode p=dhead.next;while (p!=null && !p.data.equals(e)){j++;//查找元素ep=p.next;}if (p==null)//未找到时返回-1return -1;elsereturn j;//找到后返回其序号}10、在线性表中序号i位置插入元素e
public void Insert(int i, E e)//在线性表中序号i位置插入元素e{if (isize())//参数错误抛出异常throw new IllegalArgumentException("插入:位置i不在有效范围内");DLinkNode s=new DLinkNode(e);//建立新结点sDLinkNode p=dhead=geti(i-1);//找到序号为i-1的结点p,其后插入s结点s.next=p.next;//修改s结点的next字段if (p.next!=null)//修改p结点的非空后继结点的prior字段p.next.prior=s;p.next=s;//修改p结点的next字段s.prior=p;//修改s结点的prior字段}11、在线性表中删除序号i位置的元素
public void Delete(int i) //在线性表中删除序号i位置的元素{if (isize()-1)//参数错误抛出异常throw new IllegalArgumentException("删除:位置i不在有效范围内");DLinkNode p=geti(i);//找到序号为i的结点p,删除该结点p.prior.next=p.next;//修改p结点的前驱结点的next字段if (p.next!=null)//修改p结点非空后继结点的prior字段p.next.prior=p.prior;}12、将线性表转换为字符串
public String toString()//将线性表转换为字符串{String ans="";DLinkNode p=dhead.next;while (p!=null){ans+=p.data+" ";p=p.next;}return ans;}13、双链表完整代码
import java.util.*;@SuppressWarnings("unchecked")class DLinkNode//双链表结点泛型类{E data;DLinkNode prior;//前驱结点指针DLinkNode next;//后继结点指针public DLinkNode()//构造方法{prior=null;next=null;}public DLinkNode(E d)//重载构造方法{data=d;prior=null;next=null;}}public class DLinkListClass//双链表泛型类{DLinkNode dhead;//存放头结点public DLinkListClass()//构造方法{dhead=new DLinkNode();//创建头结点dhead.prior=null;dhead.next=null;}private DLinkNode geti(int i)//返回序号为i的结点{DLinkNode p=dhead;int j=-1;while (j<i){j++;p=p.next;}return p;}//线性表的基本运算算法public void CreateListF(E[] a)//头插法：由数组a整体建立双链表{DLinkNode s;for (int i=0;i<a.length;i++)//循环建立数据结点s{s=new DLinkNode(a[i]);//新建存放a[i]元素的结点s，将其插入到表头s.next=dhead.next;//修改s结点的next字段if (dhead.next!=null)//修改头结点的非空后继结点的prior字段dhead.next.prior=s;dhead.next=s;//修改头结点的next字段s.prior=dhead;//修改s结点的prior字段}}public void CreateListR(E[] a)//尾插法：由数组a整体建立双链表{DLinkNode s,t;t=dhead;//t始终指向尾结点,开始时指向头结点for (int i=0;i<a.length;i++)//循环建立数据结点s{s=new DLinkNode(a[i]);//新建存放a[i]元素的结点st.next=s;//将s结点插入t结点之后s.prior=t; t=s;}t.next=null;//将尾结点的next字段置为null}public void Add(E e)//在线性表的末尾添加一个元素e{DLinkNode s=new DLinkNode(e);//新建结点sDLinkNode p=dhead;while (p.next!=null)//查找尾结点pp=p.next;p.next=s;//在尾结点之后插入结点ss.prior=p;}public int size()//求线性表长度{DLinkNode p=dhead;int cnt=0;while (p.next!=null)//找到尾结点为止{cnt++;p=p.next;}return cnt;}public void Setsize(int nlen)//设置线性表的长度{int len=size();if (nlenlen)throw new IllegalArgumentException("设置长度:n不在有效范围内");if (nlen==len) return;DLinkNode p=geti(nlen-1);//找到序号为nlen-1的结点pp.next=null;//将结点p置为尾结点}public E GetElem(int i)//返回线性表中序号为i的元素{int len=size();if (ilen-1)throw new IllegalArgumentException("查找:位置i不在有效范围内");DLinkNode p=geti(i);//找到序号为i的结点preturn (E)p.data;}public void SetElem(int i,E e)//设置序号i的元素为e{if (isize()-1)throw new IllegalArgumentException("设置:位置i不在有效范围内");DLinkNode p=geti(i);//找到序号为i的结点pp.data=e;}public int GetNo(E e)//查找第一个为e的元素的序号{int j=0;DLinkNode p=dhead.next;while (p!=null && !p.data.equals(e)){j++;//查找元素ep=p.next;}if (p==null)//未找到时返回-1return -1;elsereturn j;//找到后返回其序号}public void Insert(int i, E e)//在线性表中序号i位置插入元素e{if (isize())//参数错误抛出异常throw new IllegalArgumentException("插入:位置i不在有效范围内");DLinkNode s=new DLinkNode(e);//建立新结点sDLinkNode p=dhead=geti(i-1);//找到序号为i-1的结点p,其后插入s结点s.next=p.next;//修改s结点的next字段if (p.next!=null)//修改p结点的非空后继结点的prior字段p.next.prior=s;p.next=s;//修改p结点的next字段s.prior=p;//修改s结点的prior字段}public void Delete(int i) //在线性表中删除序号i位置的元素{if (isize()-1)//参数错误抛出异常throw new IllegalArgumentException("删除:位置i不在有效范围内");DLinkNode p=geti(i);//找到序号为i的结点p,删除该结点p.prior.next=p.next;//修改p结点的前驱结点的next字段if (p.next!=null)//修改p结点非空后继结点的prior字段p.next.prior=p.prior;}public String toString()//将线性表转换为字符串{String ans="";DLinkNode p=dhead.next;while (p!=null){ans+=p.data+" ";p=p.next;}return ans;}}好啦！内容有点多！！！到此链表的内容已经学习完毕，学会上面全部内容，分分钟手撕链表不是问题！！！
关注我，持续更新数据结构与算法的内容，感兴趣的可以关注我的专栏！