//带头结点的单链表类
//建议，不声明成员变量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)
*/
分享到：
相关推荐
本话题主要探讨两种常用的数据结构——单链表和双向链表在Java中的实现，以及相关的操作，如在头部添加节点、在尾部添加节点、遍历、逆置和删除。 首先，我们来理解单链表和双向链表的基本概念。单链表是一种线性...
本文将深入探讨Java中链表的操作实例，旨在帮助开发者更好地理解和运用链表来解决实际问题。 首先，我们需要理解链表的基本概念。链表不同于数组，它不连续存储元素，每个元素（称为节点）包含数据以及指向下一个...
在这个链表演示程序中，我们看到一个用Java语言实现的链表，它是针对数据结构课程设计的一个项目。这个项目的目标是帮助学生理解和实践链表的基本操作，如初始化、插入、删除和搜索。 首先，让我们深入了解链表的...
Java链表是一种基础且重要的数据结构，主要用于存储和管理动态数据集合。在Java中，有多种类型的链表，包括单链表、双链表和循环链表等。本程序可能是针对这些链表类型的一种实现，用于Java考试复习。在Java中，`...
Java链表是编程中一种基础且重要的数据结构，它在许多场景下有着广泛的应用。本文将结合个人学习心得，深入探讨Java链表的核心概念、实现方式以及与其他编程语言的互通性。 首先，链表是一种线性数据结构，与数组...
总结来说，用Java链表实现多项式相加和相乘，主要步骤包括： 1. 创建`Node`类，表示多项式项。 2. 创建`LinkedList`类，表示多项式链表，并实现链表的基本操作。 3. 实现`insertA`方法，将一个多项式插入到另一个...
用java实现了数据结构中的链表，作为新手学习数据结构和java的资料。
"JAVA单链表操作实验" 在本实验中，我们将实现一个基于JAVA的单链表操作实验，该实验可以实现以下三个功能：1.根据从键盘输入一串字符串自动生成一个单链表；2.根据指定元素删除相应的结点，可以一次性删除多个结点...
本实例聚焦于Java中的一个重要数据结构——双向链表，它在很多场景下都有着广泛的应用。双向链表与单链表相比，其独特之处在于每个节点不仅包含指向下一个节点的指针，还包含指向前一个节点的指针，这使得在链表中的...
在这个“链表操作演示程序Java版”中，我们看到开发者利用Java语言和JavaFX库创建了一个可视化工具，用于展示链表的各种操作。JavaFX是一个用于构建桌面、移动和嵌入式平台的富客户端应用程序的开源框架。 1. **...
至于`TestShape.java`，这可能是一个测试类，用于实例化`LinkList`并执行各种操作，比如添加元素、删除元素、打印链表等，以验证链表功能的正确性。例如： ```java public class TestShape { public static void ...
- 在Java中，我们可以创建一个Node类来表示链表节点，包含一个data字段和一个next字段。 ```java public class Node { int data; Node next; public Node(int data) { this.data = data; this.next = null; ...
在Java编程语言中，链表是一种重要的数据...以上就是关于Java语言中单链表实现的知识点，涵盖了链表的基本概念、类结构、操作方法以及实际应用。理解这些概念有助于更好地设计和优化程序，特别是在处理动态数据集时。
本文将深入探讨如何使用Java语言实现单链表的基本操作，包括创建链表、插入节点、删除节点以及遍历链表等关键功能。 首先，我们需要理解单链表的概念。单链表是一种线性数据结构，其中每个元素（称为节点）包含两个...
在“java链表反转及排序”这个主题中，我们将探讨如何在Java中实现单向链表的反转和排序。首先，我们创建一个链表节点类，包含数据和指向下一个节点的引用： ```java public class ListNode { int val; // 节点值 ...
本教程将深入探讨如何使用Java语言来实现单链表及其相关操作。 首先，我们来理解单链表的基本概念。单链表由一系列节点组成，每个节点包含两部分：数据域（用于存储数据）和指针域（指向下一个节点）。链表的最后一...
接下来，`StringLinkedList.java`文件应该实现了基于`ListNode`的链表操作。这是一个字符串链表，意味着每个节点可能包含一个字符串。一个简单的`StringLinkedList`类可能包含以下方法： 1. **构造函数**：初始化空...
链表 链表_基于Java的单链表基本操作之链表相交
链表 链表_基于Java的单链表基本操作之链表排序
链表 链表_基于Java的单链表基本操作之链表反转