//带头结点的单链表类
//建议，不声明成员变量rear和n，不安全，维护困难，子类需要同时修改3个成员变量，易出错。
package dataStructure.linearList;
import dataStructure.linearList.Node; //导入单链表结点类
import java.util.Iterator; //导入迭代器接口
public class HSLinkedList<E> extends AbstractList<E> implements LList<E> //带头结点的单链表类，实现线性表接口
{
protected Node<E> head; //头指针，指向单链表的头结点
protected Node<E> rear; //尾指针，指向单链表最后一个结点
protected int n; //单链表长度
public HSLinkedList() //构造空链表
{
this.head = new Node<E>(); //创建头结点，值为null
this.rear = this.head;
this.n=0;
}
public boolean isEmpty() //判断单链表是否为空，O(1)
{
return this.head.next==null;
}
public int length() //返回单链表长度，O(1)
{
return this.n;
}
public E get(int index) //返回序号为index的对象，index初值为0
{ //若单链表空或序号错误返回null，O(n)
if (index>=0)
{
int j=0;
Node<E> p=this.head.next;
while (p!=null && j<index)
{
j++;
p = p.next;
}
if (p!=null)
return (E)p.data;
}
return null;
}
public E set(int index, E element) //设置序号为index的对象为element，O(n)
{ //若操作成功返回原对象，否则返回null
if (index>=0 && element!=null)
{
int j=0;
Node<E> p=this.head.next;
while (p!=null && j<index)
{
j++;
p = p.next;
}
if (p!=null)
{
E old = (E)p.data;
p.data = element;
return old; //若操作成功返回原对象
}
}
return null; //操作不成功
}
public boolean add(E element) //在单链表最后添加对象，O(1)
{
if (element==null)
return false;
this.rear.next = new Node<E>(element); //尾插入
this.rear = this.rear.next; //移动尾指针
this.n++;
return true;
}
public boolean add(int index, E element) //在指定位置插入非空的指定对象
{ //若操作成功返回true，O(n)
if (element==null)
return false;
if (index>=this.n)
return this.add(element); //插入在最后
else
{
int j=0;
Node<E> p = this.head;
while (p.next!=null && j<index) //若index<=0，插入在头结点之后
{
j++;
p = p.next;
}
p.next=new Node<E>(element, p.next); //插入在p结点之后，包括头插入、中间插入
this.n++;
return true;
}
}
public E remove(int index) //移去index位置的对象，O(n)
{ //若操作成功返回被移去对象，否则返回null
E old = null;
if (index>=0) //头删除、中间/尾删除
{
int j=0;
Node<E> p=this.head;
while (p.next!=null && j<index) //定位到待删除结点的前驱结点
{
j++;
p = p.next;
}
if (p.next!=null)
{
old = (E)p.next.data;
if (p.next==this.rear)
this.rear=p;
p.next = p.next.next; //删除p的后继结点
this.n--;
}
}
return old;
}
public void clear() //清空单链表，O(1)
{
this.head.next = null;
this.rear = this.head;
this.n=0;
}
public String toString() //返回显示单链表所有元素值对应的字符串
{ //单链表遍历算法，O(n)
String str="(";
Node<E> p = this.head.next;
while (p!=null)
{
str += p.data.toString();
p = p.next;
if (p!=null)
str += ", ";
}
return str+")";
}
//以上实现LList接口
public Iterator<E> iterator() //返回一个迭代器对象
{
return new Itr();
}
private class Itr implements Iterator<E> //私有内部类，实现迭代器接口
{
private Node<E> cursor = head.next;
public boolean hasNext() //若有后继元素，返回true
{
return cursor!=null && cursor.next!=null;
}
public E next() //返回后继元素
{
if (cursor != null && cursor.next!=null)
{
E element = cursor.next.data;
cursor = cursor.next;
return element;
}
return null;
}
public void remove() //不支持该操作
{
throw new UnsupportedOperationException();
}
}//内部类Itr结束
public static void main(String args[])
{
HSLinkedList<String> list = new HSLinkedList<String>();
for (int i=5; i>=0; i--)
list.add(0,new String((char)('A'+i)+""));
System.out.println(list.toString());
}
}
/*
程序运行结果如下：
(A, B, C, D, E, F)
*/
分享到：
相关推荐
操作包括： 1. 在头部添加结点 2. 在尾部添加结点 3. 遍历 4. 逆置 5. 删除
一个java实例，用来描述java算法中链表的使用。
用java编写的链表演示软件源代码，实现了链表的初始化，插入，删除，搜索功能等，导入工程可直接使用。
用java实现了数据结构中的链表，作为新手学习数据结构和java的资料。
Java实现单链表的基本操作
java语言对链表的基本操作，包括增加节点，查找结点，删除节点，更新节点四种操作
通过Java实现单链表的操作，包括单链表定义、遍历、置空、判空、插入、删除、反转、中间结点、指定顺序排序、前插、后插、判断单链表是否存在环、环的长度、环的起始结点
本代码可实现以下功能： 1.根据从键盘输入一串字符串自动生成一个单链表 2.根据指定元素删除相应的结点，可一次性删除多个结点 3.根据指定修改相应结点的元素值，可一次性同时修改多个相同结点值得 ...
Java算法实例-双向链表操作，封装性高，考试、学习都可使用
用java实现双向链表的完整操作，主要用到内部类实现。
java单链表操作，封装性高，方便查看，考试、学习都可使用
使用的Java语言和JavaFX库编写的链表操作演示程序源码，对于链表的几个基本操作都具有演示动画，且数据可数据产生，也可以随机产生
链表是一种物理存储单元上非连续、非顺序的存储结构。 java代码实现单链表，插入，删除和遍历等功能。 链表能够灵活的进行插入和删除操作，时间复杂度为O（1）,链表的查找时间复杂度为O（n）。
用Java定义一个双向链表，实现链表的基本操作： 初始化、获取头结点、添加新元素、删除链表元素、 获取链表元素、查找链表元素、更新链表中某个元素、 判断链表是否为空、求链表元素个数、输出链表元素、清空链表。
用Java定义一个循环链表，实现链表的基本操作： 初始化*、获取头结点、添加新元素*、删除链表元素 、获取链表元素*、查找链表元素*、更新链表中某个元素、 判断链表是否为空、求链表元素个数、输出链表元素、清空...
JAVA链表的介绍（包含单项链表、双向链表）、LinkedList 与 ArrayList 比较、链表的基本操作、基本方法等
链表操作程序(完整)C语言.txt链表操作程序(完整)C语言.txt
和文章的Java链表相匹配，里面的步骤都分级了，可以按照步骤写就可以实现java链表的增删改查等操作第一次制作可能有些简陋，但是还是挺清晰的，刚学的可以看一下，这个也是我刚学的时候写的笔记，比较通俗易懂都是...
这是一个数据结构课程设计的程序！里面包含了单链表的所有操作（插入 删除 排序 打印等等）两个链表的运算（交 并 差）！
java链表操作的基本单元-结点类的定义，包括数据域和指针域，望大神们指点