java数据结构与算法之顺序表与链表深入分析
java数据结构与算法之顺序表与链表深
入分析
1.线性表抽象数据类型概述
首先来说明一下什么是抽象数据类型，我们都知道java在默认情况下，所有的基本数据类型(int,float,boolean等)都支持基本运算，如加减法，这是因为系统已帮我们实现了这些基本数据类型的的基本运算。而对于自定义的数据类型(如类)也需要定义相应的运算，但在实际使用这些自定义的数据类型的运算时需要自己实现相关的运算，也就是说用户自定义的数据类型的运算需要我们自己利用系统提供的基本运算来定义和实现。这些自定义了数据结构(如自定义类)和包含相关运算组合实现的数据类型就称其为抽象数据类型(ADT,Abstract Data Type),因此一个ADT会包含数据声明和运算声明。常用的ADT包含链表、栈、队列、优先队列、二叉树、散列表、图等，所以接下来我们要分析的顺序表和链表也属于ADT范畴。下面引用自java数据结构一书对线性表的定义:
线性表是由n(n>=0)个类型相同的数据元素a0,a1,…,an-1组成的有限的序列，在数学中记作(a0,a1,…,an-1)，其中ai的数据类型可以是基本数据类型(int,float等)、字符或类。n代表线性表的元素个数，也称其为长度(Length)。若n=0，则为空表;若n > 0，则ai(0 < i < n-1)
有且仅有一个前驱(Predecessor)元素ai-1和一个后继(Successor)元素ai+1，a0没有前驱元素，ai没有后继元素。
以上便是对线性表抽象数据类型概述，下面我们开始分别针对顺序表和链表进行深入分析。
2.线性表的顺序存储设计与实现(顺序表)
2.1 顺序存储结构的设计原理概要
顺序存储结构底层是利用数组来实现的，而数组可以存储具有相同数据类型的元素集合，如int，float或者自定义类型等，当我们创建一个数组时，计算机操作系统会为该数组分配一块连续的内存块，这也就意味着数组中的每个存储单元的地址都是连续的，因此只要知道了数组的起始内存地址就可以通过简单的乘法和加法计算出数组中第n-1个存储单元的内存地址，就如下图所示:
通过上图可以发现为了访问一个数组元素，该元素的内存地址需要计算其距离数组基地址的偏移量，即用一个乘法计算偏移量然后加上基地址，就可以获得数组中某个元素的内存地址。其中c代表的是元素数据类型的存储空间大小，而序号则为数组的下标索引。整个过程需要一次乘法和一次加法运算，因为这两个操作的执行时间是常数时间，所以我们可以认为数组访问操作能再常数时间内完成，即时间复杂度为O(1)，这种存取任何一个元素的时间复杂度为O(1)的数据结构称之为随机存取结构。而顺序表的存储原理正如上图所示，因此顺序
表的定义如下(引用):
线性表的顺序存储结构称之为顺序表(Sequential List),它使用一维数组依次存放从a0到an-1的数据元素(a0,a1,…,an-1)，将ai(0< i <> n-1)存放在数组的第i个元素，使得ai与其前驱ai-1及后继ai+1的存储位置相邻，因此数据元素在内存的物理存储次序反映了线性表数据元素之间的逻辑次序。
2.2 顺序存储结构的实现分析
接着我们来分析一下顺序表的实现，先声明一个顺序表接口类ISeqList
，然后实现该接口并实现接口方法的代码，ISeqList接口代码如下:
package com.zejian.structures.LinkedList;
/**
* Created by zejian on 2016/10/30.
* 顺序表顶级接口
*/
public interface ISeqList {
/**
* 判断链表是否为空
* @return
*/
boolean isEmpty();
/**
* 链表长度
* @return
*/
int length();
/**
* 获取元素
* @param index
* @return
*/
T get(int index);
/**
* 设置某个元素的值
* @param index
* @param data
* @return
*/
T set(int index, T data);
/**
* 根据index添加元素
* @param index
* @param data
* @return
*/
boolean add(int index, T data);
/**
* 添加元素
* @param data
* @return
*/
boolean add(T data);
/**
* 根据index移除元素
* @param index
* @return
*/
T remove(int index);
/**
* 根据data移除元素
* @param data
* @return
*/
boolean remove(T data);
/**
* 根据data移除元素
* @param data
* @return
*/
boolean removeAll(T data);
/**
* 清空链表
*/
void clear();
/**
* 是否包含data元素
* @param data
* @return
*/
boolean contains(T data);
/**
* 根据值查询下标
* @param data
* @return
*/
int indexOf(T data);
/**
* 根据data值查询最后一个出现在顺序表中的下标
* @param data
* @return
*/
int lastIndexOf(T data);
/**
* 输出格式
* @return
*/
String toString();
}
}
代码中声明了一个Object数组，初始化数组大小默认为64，存储的元素类型为泛型T，length则为顺序表的长度，部分方法实现比较简单，这里不过多分析，我们主要分析get(int index)、set(int index, T data)、add(int index, T data)、remove(int index)、removeAll(T data)、indexof(T data)
等方法的实现。
get(int index) 实现分析
从顺序表中获取值是一种相当简单的操作并且效率很高，这是由于顺序表内部采用了数组作为存储数据的容器。因此只要根据传递的索引值，然后直接获取数组中相对应下标的值即可，代码实现如下:
public T get(int index){
if (index>=0 && index=0 && indexthis.length)
index = this.length;
//判断内部数组是否已满
if (this.length==table.length)
{
//把原数组赋值给临时数组
Object[] temp = this.table;
//对原来的数组进行成倍拓容,并把原数组的元素复制到新数组
this.table = new Object[temp.length*2];
//先把原数组下标从0到index-1(即插入位置的前一个位置)复制到新数组
for (int i=0; i=index; j--) {
this.table[j + 1] = this.table[j];
}
//插入新值
this.table[index] = data;
//长度加一
this.length++;
//插入成功
return true;
}
remove(int index) 实现分析
顺序表的删除操作和前的插入操作情况是类似的，如果是在中间或者头部删除顺序表中的元素，那么在删除位置之后的元素都必须依次往前移动，效率较低，如果是在顺序表的尾部直接删除的话，则无需移动元素，此情况下删除效率高。如下图所示在顺序表中删除元素ai时，ai之后的元素都依次往前移动:
删除操作的代码实现如下:
/**
* 根据index删除元素
* @param index 需要删除元素的下标
* @return
*/
public T remove(int index)
{
if (this.length!=0 && index>=0 && index=0; i--)
if (data.equals(this.table[i]))
return i;
return -1;
}
以上便是顺序表的主要的操作方法，当然顺序表中还可以实现其他操作，如在初始化构造函数时传入数组来整体初始化顺序表，比较两个信息表是否相等、是否包含某个数据等。这里贴一下传入数据构建顺序表构造方法实现，其他实现代码我们这里就不贴了，稍后实现源
码都会上传gitHub提供给大家:
/**
* 传入一个数组初始化顺序表
* @param array
*/
public SeqList(T[] array){
if (array==null){
throw new NullPointerException("array can\'t be empty!");
}
//创建对应容量的数组
this.table = new Object[array.length]; //复制元素
for (int i=0;i
题
快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题
，主要针对获取、插入、修改、删除等主要操作。前面分析过，由于顺序表内部采用了数组作为存储容器，而数组又是随机存取结构的容器，也就是说在创建数组时操作系统给数组分配的是一块连续的内存空间，数组中每个存储单元的地址都是连续的，所以在知道数组基地址后可以通过一个简单的乘法和加法运算即可计算出其他存储单元的内存地址(实际上计算机内部也就是这么做的)，这两个运算的执行时间是常数时间，因此可以认为数组的访问操作能在常数时间内完成，即顺序表的访问操作(获取和修改元素值)的时间复杂为O(1)。
对于在顺序表中插入或者删除元素，从效率上则显得不太理想了，由于插入或者删除操作是基于位置的，需要移动数组中的其他元素，所以顺序表的插入或删除操作，算法所花费的时间主要是用于移动元素，如在顺序表头部插入或删除时，效率就显得相当糟糕了。若在最前插入或删除，则需要移动n(这里假设长度为n)个元素;若在最后插入或删除，则需要移动的元素为0。这里我们假设插入或删除值为第i(0 {
public T data;//数据域
public Node next;//地址域
public Node(T data){
this.data=data;
}
public Node(T data,Node next){
this.data=data;
this.next=next;
}
}
接着顶级的链表接口ILinkedList，该接口声明了我们所有需要实现的方法。
/**
* Created by zejian on 2016/10/21.
* 链表顶级接口
*/
public interface ILinkedList {
/**
* 判断链表是否为空
* @return
*/
boolean isEmpty();
/**
* 链表长度
* @return
*/
int length();
/**
* 获取元素
* @param index
* @return
*/
T get(int index);
/**
* 设置某个结点的的值
* @param index
* @param data
* @return
*/
T set(int index, T data);
/**
* 根据index添加结点
* @param index
* @param data
* @return
*/
boolean add(int index, T data);
/**
* 添加结点
* @param data
* @return
*/
boolean add(T data);
/**
* 根据index移除结点
* @param index
* @return
*/
T remove(int index);
/**
* 根据data移除结点
* @param data
* @return
*/
boolean removeAll(T data);
/**
* 清空链表
*/
void clear();
/**
* 是否包含data结点
* @param data
* @return
*/
boolean contains(T data);
/**
* 输出格式
* @return
*/
String toString();
}
创建一个单链表SingleILinkedList并实现ILinkedList接口，覆盖其所有方法，声明一个单链
表的头结点head，代表链表的开始位置，如下:
public class SingleILinkedList implements ILinkedList {
protected Node headNode; //带数据头结点
public SingleILinkedList(Node head) {
this.headNode = head;
}
//其他代码先省略
.....
}
boolean isEmpty()实现分析
需要判断链表是否为空的依据是头结点head是否为null，当head=null时链表即为空链表，
因此我们只需判断头结点是否为空即可，isEmpty方法实现如下:
/**
* 判断链表是否为空
* @return
*/
@Override
public boolean isEmpty() {
return this.head==null;
}
int length()实现分析
由于单链表的结点数就是其长度，因此我们只要遍历整个链表并获取结点的数量即可获取到链表的长度。遍历链表需要从头结点HeadNode开始，为了不改变头结点的存储单元，声明变量p指向当前头结点和局部变量length，然后p从头结点开始访问，沿着next地址链到达后继结点，逐个访问，直到最后一个结点，每经过一个结点length就加一，最后length的大小就是链表的大小。实现代码如下:
@Override
public int length() {
int length=0;//标记长度的变量
Node p=head;//变量p指向头结点
while (p!=null){
length++;
p=p.next;//后继结点赋值给p，继续访问
}
return length;
}
T get(int index)实现分析
在单链表中获取某个元素的值是一种比较费时间的操作，需要从头结点开始遍历直至传入值index指向的位置，其中需要注意的是index是从0开始计算，也就是说传递的index=3时，查找的是链表中第4个位置的值。其查询获取值的过程如下图所示:
代码实现如下:
/**
* 根据index索引获取值
* @param index 下标值起始值为0
* @return
*/
@Override
public T get(int index) {
if(this.head!=null&&index>=0){
int count=0;
Node p=this.head;
//找到对应索引的结点
while (p!=null&&count=0&&data!=null){
Node pre=this.head;
int count=0;
//查找需要替换的结点
while (pre!=null&&count(x,null);
b.在链表的表头插入一个新结点(即链表的开始处)，此时表头head!=null，因此head后继指
针next应该指向新插入结点p，而p的后继指针应该指向head原来的结点，代码如下:
//创建新结点
Node p =new Node(x,null); //p的后继指针指向head原来的结点
p.next=head;
//更新head
head=p;
以上代码可以合并为如下代码:
//创建新结点，其后继为head原来的结点，head的新指向为新结点 head=new Node(x,head);
c.在链表的中间插入一个新结点p，需要先找到给定插入位置的前一个结点，假设该结点为front，然后改变front的后继指向为新结点p，同时更新新结点p的后继指向为front原来的后继结点，即front.next，其执行过程如下图所示:
代码实现如下:
//新结点p
Node p =new Node(x,null); //更新p的后继指向
p.next=front.next;
//更新front的后继指向
front.next=p;
以上三句代码合并为一句简洁代码:
front.next=new Node(x,front.next);
d.在链表的表尾插入一个新结点(链表的结尾)在尾部插入时，同样需要查找到插入结点P的前一个位置的结点front(假设为front)，该结点front为尾部结点，更改尾部结点的next指针指向新结点P，新结点P的后继指针设置为null，执行过程如下:
其代码语句如下:
//front的next指针指向新结点，新结点的next指针设置为null
front.next=new Node(x,null);
到此我们也就可以发现单向链表中的中间插入和尾部插入其实可以合并为一种情况。最后这里给出该方法整体代码实现，从代码实现上来看中间插入和尾部插入确实也视为同种情况处理了。
/**
* 根据下标添加结点
* 1.头部插入
* 2.中间插入
* 3.末尾插入
* @param index 下标值从0开始
* @param data
* @return
*/
@Override
public boolean add(int index, T data) {
if (data==null){
return false;
}
//在头部插入
if (this.head==null||index<=1){
this.head = new Node(data, this.head);
}else {
//在尾部或中间插入
int count=0;
Node front=this.head;
//找到要插入结点位置的前一个结点
while (front.next!=null&&count(data,front.next);
}
return true;
}
T remove(int index) 删除结点实现分析
在单向链表中，根据传递index位置删除结点的操作分3种情况，并且删除后返回被删除结点的数据:
a. 删除链表头部(第一个)结点，此时需要删除头部head指向的结点，并更新head的结
点指向，执行图示如下:
b.
c. 代码实现如下:
d.
e. //头部删除，更新head指向
f. head=head.next;
b.删除链表的中间结点，与添加是同样的道理，需要先找到要删除结点r(假设要删除的结点为r)位置的前一个结点front(假设为front)，然后把front.next指向r.next即要删除结点的下一个结点，执行过程如下:
代码语句如下:
Node r =front.next;
//更新结点指针指向
front.next=r.next;
r=www.shanxiwang.netnull;
c.删除链表的最后一个结点，通过遍历操作找到最后一个结点r的前一个结点front，并把front.next设置为null，即可。执行过程如下:
代码如下:
front.next=null;
r=null;
我们把中间删除和尾部删除合并为如下代码:
Node r =front.next;
//如果不是尾部结点，更新结点front指针指向
if(r=!null){
front.next=r.next;
r=null;
}
该方法整体代码实现如下:
/**
* 根据索引删除结点
* @param index
* @return
*/
@Override
public T remove(int index) {
T old=null;
if (this.head!=null&&index>=0){
//直接删除的是头结点
if(index==0){
old=this.head.data;
this.head=this.head.next;
}else {
Node front = this.head;
int count = 0;
//查找需要删除结点的前一个结点
while (front.next != null && count < index - 1) {
front = front.next;
count++;
}
//获取到要删除的结点
Node r = front.next;
if ( r!= null) {
//获取旧值
old =r.data;
//更改指针指向
front.next=r.next;
//释放
r=null;
}
}
}
return old;
}
当然还有如下更简洁的代码写法:
@Override
public T remove(int index) {
T old=null;
if (this.head!=null&&index>=0){
//直接删除的是头结点
if(index==0){
old=this.head.data;
this.head=this.head.next;
}else {
Node front = this.head;
int count = 0;
//查找需要删除结点的前一个结点
while (front.next != null && count < index - 1) {
front = front.next;
count++;
}
if ( front.next!= null) {
//获取旧值
old =front.next.data;
//更改指针指向
front.next=front.next.next;
}
}
}
return old;
}
void clear() 实现分析
清空链表是一件非常简单的事，只需让head=null即可;代码如下:
/**
* 清空链表
*/
@Override
public void clear() {
this.head=null;
}
ok~,到此单链表主要的添加、删除、获取值、设置替换值、获取长度等方法已分析完毕，其他未分析的方法都比较简单这里就不一一分析了，单链表的整体代码最后会分享到github给大家。
3.3 带头结点的单链表以及循环单链表的实现
带头结点的单链表
前面分析的单链表是不带特殊头结点的，所谓的特殊头结点就是一个没有值的结点即:
//没有带值的头结点
Node head= new Node(null,null);
此时空链表的情况如下:
那么多了头结点的单向链表有什么好处呢,通过对没有带头结点的单链表的分析，我们可以知道，在链表插入和删除时都需要区分操作位，比如插入操作就分头部插入和中间或尾部插入两种情况(中间或尾部插入视为一种情况对待即可)，如果现在有不带数据的头结点，那
么对于单链表的插入和删除不再区分操作的位置，也就是说头部、中间、尾部插入都可以视为一种情况处理了，这是因为此时头部插入和头部删除无需改变head的指向了，头部插入如下所示:
因此无论是插入还是删除，在有了不带数据的头结点后，在插入或者删除时都无需区分操作位了，好~，到此我们来小结一下带头结点的单链表特点:
a.空单链表只有一个结点，head.next=null。
b.遍历的起点为p=head.next。
c.头部插入和头部删除无需改变head的指向。
同时为了使链表在尾部插入时达到更加高效，我们可在链表内增加一个尾部指向的结点rear，如果我们是在尾部添加结点，那么此时只要通过尾部结点rear进行直接操作即可，无需从表头遍历到表尾，带尾部结点的单链表如下所示:
从尾部直接插入的代码实现如下:
/**
* 尾部插入
* @param data
* @return
*/
@Override
public boolean add(T data) {
if (data==null)
throw new NullPointerException("data can\'t be empty!");
this.rear.next = new Node(data);
//更新末尾指针的指向
this.rear = this.rear.next;
return true;
}
从代码和图示看来确实只要获取当前的尾部指向的结点rear并把新结点赋值给rear.next，最后更新rear结点的值即可，完全不用遍历操作，但是如果是根据index来插入的还，遍历部分结点还是少不了的，下面看看根据index插入的代码实现，由于有了头结点，头部、中间、尾部插入无需区分操作位都视为一种情况处理。
/**
* 根据下标添加结点
* 1.头部插入
* 2.中间插入
* 3.末尾插入
* @param index 该值从0开始,如传4就代表插入在第5个位置
* @param data
* @return
*/
@Override
public boolean add(int index, T data) {
if (data==null){
throw new NullPointerException("data can\'t be empty!");
}
if(index<0)
throw new NullPointerException("index can\'t less than 0");
//无需区分位置操作,中间/头部/尾部插入
int j=0;
Node pre=this.headNode;
//查找到插入位置即index的前一个结点
while (pre.next!=null&&j q=new Node(data,pre.next);
//更改指针指向
pre.next=q;
//如果是尾部指针
if (pre==this.rear)
this.rear=q;
return true;
}
最后在看看删除的代码实现，由于删除和插入的逻辑和之前不带头结点的单链表分析过的原理的是一样的，因此我们这里不重复了，主要注意遍历的起始结点变化就行。
/**
* 根据索引删除结点
* @param index
* @return
*/
@Override
public T remove(int index) {
T old=null;
//无需区分头删除或中间删除或尾部删除的情况
if (index>=0){
Node pre = this.headNode;
int j = 0;
//查找需要删除位置的前一个结点
while (pre.next != null && j < index) {
pre = pre.next;
j++;
}
//获取到要删除的结点
Node r = pre.next;
if (r != null) {
//获取旧值
old =r.data;
//如果恰好是尾部结点,则更新rear的指向
if (r==this.rear){
this.rear=pre;
}
//更改指针指向
pre.next=r.next;
}
}
return old;
}
ok~，关于带头结点的单向链表就分析到这，这里贴出实现源码，同样地，稍后在github上也会提供:
package com.zejian.structures.LinkedList.singleLinked;
import com.zejian.structures.LinkedList.ILinkedList;
/**
* Created by zejian on 2016/10/22. * 带头结点并含有尾指针的链表
*/
public class HeadSingleILinkedList implements ILinkedList {
protected Node headNode; //不带数据头结点
protected Node rear;//指向尾部的指针
public HeadSingleILinkedList() {
//初始化头结点与尾指针
this.headNode =rear= new Node<>(null);
}
public HeadSingleILinkedList(Node head) {
this();
this.headNode.next =rear.next= head;
rear=rear.next;//更新末尾指针指向
}
/**
* 传入一个数组,转换成链表
* @param array
*/
public HeadSingleILinkedList(T[] array)
{
this();
if (array!=null && array.length>0)
{
this.headNode.next = new Node(array[0]);
rear=this.headNode.next;
int i=1;
while (i(array[i++]);
rear = rear.next;
}
}
}
/**
* 通过传入的链表构造新的链表
* @param list
*/
public HeadSingleILinkedList(HeadSingleILinkedList list) {
this();
if (list!=null && list.headNode.next!=null)
{
this.headNode.next = new Node(list.headNode.data);
Node p = list.headNode.next;
rear = this.headNode.next;
while (p!=null)
{
rear.next = new Node(p.data);
rear = rear.next;
p = p.next;
}
}
}
/**
* 判断链表是否为空
* @return
*/
@Override
public boolean isEmpty() {
return this.headNode.next==null;
}
@Override
public int length() {
int length=0;
Node currentNode=headNode.next;
while (currentNode!=null){
length++;
currentNode=currentNode.next;
}
return length;
}
/**
* 根据index索引获取值
* @param index 下标值起始值为0
* @return
*/
@Override
public T get(int index) {
if(index>=0){
int j=0;
Node pre=this.headNode.next;
//找到对应索引的结点
while (pre!=null&&j=0&&data!=null){
Node pre=this.headNode.next;
int j=0;
while (pre!=null&&j pre=this.headNode;
while (pre.next!=null&&j q=new Node(data,pre.next);
//更改指针指向
pre.next=q;
//如果是未指针
if (pre==this.rear)
this.rear=q;
return true;
}
/**
* 尾部插入
* @param data
* @return
*/
@Override
public boolean add(T data) {
if (data==null)
throw new NullPointerException("data can\'t be empty!");
this.rear.next = new Node(data);
//更新末尾指针的指向
this.rear = this.rear.next;
return true;
}
/**
* 根据索引删除结点
* @param index
* @return
*/
@Override
public T remove(int index) {
T old=null;
//包含了头删除或中间删除或尾部删除的情况
if (index>=0){
Node pre = this.headNode;
int j = 0;
//查找需要删除位置的前一个结点
while (pre.next != null && j < index) {
pre = pre.next;
j++;
}
//获取到要删除的结点
Node r = pre.next;
if (r != null) {
//获取旧值
old =r.data;
//如果恰好是尾部结点,则更新rear的指向
if (r==this.rear){
this.rear=pre;
}
//更改指针指向
pre.next=r.next;
}
}
return old;
}
/**
* 根据data移除所有数据相同的结点
* @param data
* @return
*/
@Override
public boolean removeAll(T data) {
boolean isRemove=false;
if(data!=null){
//用于记录要删除结点的前一个结点
Node front=this.headNode;
//当前遍历的结点
Node pre=front.next;
//查找所有数据相同的结点并删除
while (pre!=null){
if(data.equals(pre.data)){
//如果恰好是尾部结点,则更新rear的指向
if(data.equals(rear.data)){
this.rear=front;
}
//相等则删除pre并更改指针指向
front.next=pre.next;
pre =front.next;
isRemove=true;
}else {
front=pre;
pre=pre.next;
}
}
}
return isRemove;
}
/**
* 清空链表
*/
@Override
public void clear() {
this.headNode.next=null;
this.rear=this.headNode;
}
/**
* 判断是否包含某个值
* @param data
* @return
*/
@Override
public boolean contains(T data) {
if(data!=null){
Node pre=this.headNode.next;
while (pre!=null){
if(data.equals(pre.data)){
return true;
}
pre=pre.next;
}
}
return false;
}
/**
* 从末尾连接两个链表
* @param list
*/
public void concat(HeadSingleILinkedList list)
{
if (this.headNode.next==null) {
this.headNode.next = list.headNode.next;
} else {
Node pre=this.headNode.next;
while (pre.next!=null)
pre = pre.next;
pre.next=list.headNode.next;
//更新尾部指针指向
this.rear=list.rear;
}
}
@Override
public String toString() {
String str="(";
Node pre = this.headNode.next;
while (pre!=null)
{
str += pre.data;
pre = pre.next;
if (pre!=null)
str += ", ";
}
return str+")";
}
public static void main(String[] args){
String[] letters={"A","B","C","D","E","F"};
HeadSingleILinkedList list=new HeadSingleILinkedList<>(letters);
System.out.println("list.get(3)->"+list.get(3));
System.out.println("list:"+list.toString());
System.out.println("list.add(4,Y)—>"+list.add(4,"Y"));
System.out.println("list:"+list.toString());
System.out.println("list.add(Z)—>"+list.add("Z"));
System.out.println("list:"+list.toString());
System.out.println("list.contains(Z)->"+list.contains("Z"));
System.out.println("list.set(4,P)-->"+list.set(4,"P"));
System.out.println("list:"+list.toString());
System.out.println("list.remove(Z)->"+list.removeAll("Z"));
System.out.println("list.remove(4)-->"+list.remove(4));
System.out.println("list:"+list.toString());
}
}
此时的循环单链表有如下特点:
a.当循环链表为空链表时，head指向头结点，head.next=head。
b.尾部指向rear代表最后一个结点，则有rear.next=head。
在处理循环单链表时，我们只需要注意在遍历循环链表时，避免进入死循环即可，也就是在
判断循环链表是否到达结尾时，由之前的如下判断
Node p=this.head;
while(p!=null){
p=p.next;
}
在循环单链表中改为如下判断:
Node p=this.head;
while(p!=this.head){
p=p.next;
}
因此除了判断条件不同，其他操作算法与单链表基本是一样的，下面我们给出循环单链表的代码实现:
package com.zejian.structures.LinkedList.singleLinked;
import com.zejian.structures.LinkedList.ILinkedList;
/**
* Created by zejian on 2016/10/25.
* 循环单链表
*/
public class CircularHeadSILinkedList implements ILinkedList {
protected Node head; //不带数据头结点
protected Node tail;//指向尾部的指针
public CircularHeadSILinkedList() {
//初始化头结点与尾指针
this.head= new Node(null);
this.head.next=head;
this.tail=head;
}
public CircularHeadSILinkedList(T[] array)
{
this();
if (array!=null && array.length>0)
{
this.head.next = new Node<>(array[0],head);
tail=this.head.next;
int i=1;
while (i(array[i++]);
tail.next.next=head;
tail = tail.next;
}
}
}
@Override
public boolean isEmpty() {
return this.head.next==head;
}
@Override
public int length() {
int length=0;
Node p=this.head.next;
while (p!=head){
p=p.next;
length++;
}
return length;
}
@Override
public T get(int index) {
if (index>=0)
{
int j=0;
Node pre=this.head.next;
while (pre!=null && j=0){
int j=0;
Node p=this.head.next;
while (p!=head&&j=size)
return false;
int j=0;
Node p=this.head;
//寻找插入点的位置的前一个结点
while (p.next!=head&&j q=new Node<>(data,p.next);
p.next=q;
//更新尾部指向
if(p==tail){
this.tail=q;
}
return true;
}
@Override
public boolean add(T data) {
if(data==null){
return false;
}
Node q=new Node<>(data,this.tail.next);
this.tail.next=q;
//更新尾部指向
this.tail=q;
return true;
}
@Override
public T remove(int index) {
int size=length();
if(index<0||index>=size||isEmpty()){
return null;
}
int j=0;
Node p=this.head.next;
while (p!=head&&j front=this.head;
//当前遍历的结点
Node pre=front.next;
//查找所有数据相同的结点并删除
while (pre!=head){
if(data.equals(pre.data)){
//如果恰好是尾部结点,则更新rear的指向
if(data.equals(tail.data)){
this.tail=front;
}
//相等则删除pre并更改指针指向
front.next=pre.next;
pre =front.next;
isRemove=true;
}else {
front=pre;
pre=pre.next;
}
}
return isRemove;
}
@Override
public void clear() {
this.head.next=head;
this.tail=head;
}
@Override
public boolean contains(T data) {
if (data==null){
return false;
}
Node p=this.head.next;
while (p!=head){
if(data.equals(p.data)){
return true;
}
p=p.next;
}
return false;
}
@Override
public String toString()
{
String str="(";
Node p = this.head.next;
while (p!=head)
{
str += p.data.toString();
p = p.next;
if (p!=head)
str += ", ";
}
return str+")";
}
public static void main(String[] args){
String[] letters={"A","B","C","D","E","F"};
CircularHeadSILinkedList list=new CircularHeadSILinkedList<>(letters);
System.out.println("list.get(3)->"+list.get(3));
System.out.println("list:"+list.toString());
System.out.println("list.add(4,Y)—>"+list.add(4,"Y"));
System.out.println("list:"+list.toString());
System.out.println("list.add(Z)—>"+list.add("Z"));
System.out.println("list:"+list.toString());
System.out.println("list.contains(Z)->"+list.contains("Z"));
System.out.println("list.set(4,P)-->"+list.set(4,"P"));
System.out.println("list:"+list.toString());
System.out.println("list.removeAll(Z)->"+list.removeAll("Z"));
System.out.println("list.remove(4)-->"+list.remove(4));
System.out.println("list:"+list.toString());
}
}
3.4 单链表的效率分析
由于单链表并不是随机存取结构，即使单链表在访问第一个结点时花费的时间为常数时间，但是如果需要访问第i(0
本文档为【java数据结构与算法之顺序表与链表深入分析】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。
该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。
[版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
浙公网安备 33021202002483