「链表的基本操作java」链表的基本操作实验总结
本篇文章给大家谈谈链表的基本操作java,以及链表的基本操作实验总结对应的知识点,希望对各位有所帮助,不要忘了收藏本站喔。
本文目录一览:
- 1、Java语言没有指针,怎样实现链表?
- 2、java如何实现链表
- 3、我想用JAVA实现一个链表的插入~删除等操作~ (要再界面上操作~~~ 就是我按下一个键能进行插入删除的操作的
- 4、求java 单链表基本操作的实现
- 5、java 链表的输出问题
Java语言没有指针,怎样实现链表?
Java语言中的对象引用实际上是一个指针(这里的指针均为概念上的意义,而非语言提供的数据类型),所以我们可以编写这样的类来实现链表中的结点。
private static class EntryE {
E element; // 当前存储元素
EntryE next; // 下一个元素节点
EntryE previous; // 上一个元素节点
Entry(E element, EntryE next, EntryE previous) {
this.element = element;
this.next = next;
this.previous = previous;
}
}
将数据域定义成Object类是因为Object类是广义超类,任何类对象都可以给其赋值,增加了代码的通用性。为了使链表可以被访问还需要定义一个表头,表头必须包含指向第一个结点的指针和指向当前结点的指针。为了便于在链表尾部增加结点,还可以增加一指向链表尾部的指针,另外还可以用一个域来表示链表的大小,当调用者想得到链表的大小时,不必遍历整个链表。
链表的数据结构我们可以用类List来实现链表结构,用变量Head、Tail、Length、Pointer来实现表头。
存储当前结点的指针时有一定的技巧,Pointer并非存储指向当前结点的指针,而是存储指向它的前趋结点的指针,当其值为null时表示当前结点是第一个结点,因为当删除当前结点后仍需保证剩下的结点构成链表,如果Pointer指向当前结点,则会给操作带来很大困难。如何得到当前结点呢?我们定义了一个方法cursor(),返回值是指向当前结点的指针。类List还定义了一些方法来实现对链表的基本操作,通过运用这些基本操作我们可以对链表进行各种操作。
例如reset()方法使第一个结点成为当前结点。insert(Object d)方法在当前结点前插入一个结点,并使其成为当前结点。remove()方法删除当前结点同时返回其内容,并使其后继结点成为当前结点,如果删除的是最后一个结点,则第一个结点变为当前结点。
java如何实现链表
链表是一种重要的数据结构,在程序设计中占有很重要的地位。C语言和C++语言中是用指针来实现链表结构的,由于Java语言不提供指针,所以有人认为在Java语言中不能实现链表,其实不然,Java语言比C和C++更容易实现链表结构。Java语言中的对象引用实际上是一个指针(本文中的指针均为概念上的意义,而非语言提供的数据类型),所以我们可以编写这样的类来实现链表中的结点。
class Node
{
Object data;
Node next;//指向下一个结点
}
将数据域定义成Object类是因为Object类是广义超类,任何类对象都可以给其赋值,增加了代码的通用性。为了使链表可以被访问还需要定义一个表头,表头必须包含指向第一个结点的指针和指向当前结点的指针。为了便于在链表尾部增加结点,还可以增加一指向链表尾部的指针,另外还可以用一个域来表示链表的大小,当调用者想得到链表的大小时,不必遍历整个链表。下图是这种链表的示意图:
链表的数据结构
我们可以用类List来实现链表结构,用变量Head、Tail、Length、Pointer来实现表头。存储当前结点的指针时有一定的技巧,Pointer并非存储指向当前结点的指针,而是存储指向它的前趋结点的指针,当其值为null时表示当前结点是第一个结点。那么为什么要这样做呢?这是因为当删除当前结点后仍需保证剩下的结点构成链表,如果Pointer指向当前结点,则会给操作带来很大困难。那么如何得到当前结点呢,我们定义了一个方法cursor(),返回值是指向当前结点的指针。类List还定义了一些方法来实现对链表的基本操作,通过运用这些基本操作我们可以对链表进行各种操作。例如reset()方法使第一个结点成为当前结点。insert(Object d)方法在当前结点前插入一个结点,并使其成为当前结点。remove()方法删除当前结点同时返回其内容,并使其后继结点成为当前结点,如果删除的是最后一个结点,则第一个结点变为当前结点。
链表类List的源代码如下:
import java.io.*;
public class List
{
/*用变量来实现表头*/
private Node Head=null;
private Node Tail=null;
private Node Pointer=null;
private int Length=0;
public void deleteAll()
/*清空整个链表*/
{
Head=null;
Tail=null;
Pointer=null;
Length=0;
}
public void reset()
/*链表复位,使第一个结点成为当前结点*/
{
Pointer=null;
}
public boolean isEmpty()
/*判断链表是否为空*/
{
return(Length==0);
}
public boolean isEnd()
/*判断当前结点是否为最后一个结点*/
{
if(Length==0)
throw new java.lang.NullPointerException();
else if(Length==1)
return true;
else
return(cursor()==Tail);
}
public Object nextNode()
/*返回当前结点的下一个结点的值,并使其成为当前结点*/
{
if(Length==1)
throw new java.util.NoSuchElementException();
else if(Length==0)
throw new java.lang.NullPointerException();
else
{
Node temp=cursor();
Pointer=temp;
if(temp!=Tail)
return(temp.next.data);
else
throw new java.util.NoSuchElementException();
}
}
public Object currentNode()
/*返回当前结点的值*/
{
Node temp=cursor();
return temp.data;
}
public void insert(Object d)
/*在当前结点前插入一个结点,并使其成为当前结点*/
{
Node e=new Node(d);
if(Length==0)
{
Tail=e;
Head=e;
}
else
{
Node temp=cursor();
e.next=temp;
if(Pointer==null)
Head=e;
else
Pointer.next=e;
}
Length++;
}
public int size()
/*返回链表的大小*/
{
return (Length);
}
public Object remove()
/*将当前结点移出链表,下一个结点成为当前结点,如果移出的结点是最后一个结点,则第一个结点成为当前结点*/
{
Object temp;
if(Length==0)
throw new java.util.NoSuchElementException();
else if(Length==1)
{
temp=Head.data;
deleteAll();
}
else
{
Node cur=cursor();
temp=cur.data;
if(cur==Head)
Head=cur.next;
else if(cur==Tail)
{
Pointer.next=null;
Tail=Pointer;
reset();
}
else
Pointer.next=cur.next;
Length--;
}
return temp;
}
private Node cursor()
/*返回当前结点的指针*/
{
if(Head==null)
throw new java.lang.NullPointerException();
else if(Pointer==null)
return Head;
else
return Pointer.next;
}
public static void main(String[] args)
/*链表的简单应用举例*/
{
List a=new List ();
for(int i=1;i=10;i++)
a.insert(new Integer(i));
System.out.println(a.currentNode());
while(!a.isEnd())
System.out.println(a.nextNode());
a.reset();
while(!a.isEnd())
{
a.remove();
}
a.remove();
a.reset();
if(a.isEmpty())
System.out.println("There is no Node in List \n");
System.in.println("You can press return to quit\n");
try
{
System.in.read();
//确保用户看清程序运行结果
}
catch(IOException e)
{}
}
}
class Node
/*构成链表的结点定义*/
{
Object data;
Node next;
Node(Object d)
{
data=d;
next=null;
}
}
读者还可以根据实际需要定义新的方法来对链表进行操作。双向链表可以用类似的方法实现只是结点的类增加了一个指向前趋结点的指针。
可以用这样的代码来实现:
class Node
{
Object data;
Node next;
Node previous;
Node(Object d)
{
data=d;
next=null;
previous=null;
}
}
当然,双向链表基本操作的实现略有不同。链表和双向链表的实现方法,也可以用在堆栈和队列的实现中,这里就不再多写了,有兴趣的读者可以将List类的代码稍加改动即可。
希望对你有帮助。
我想用JAVA实现一个链表的插入~删除等操作~ (要再界面上操作~~~ 就是我按下一个键能进行插入删除的操作的
编辑词条JAVA容器
解释一:
容器(Container)
Spring 提供容器功能,容器可以管理对象的生命周期、对象与对象之间的依赖关系,您可以使用一个配置文件(通常是XML),在上面定义好对象的名称、如何产生(Prototype 方式或Singleton 方式)、哪个对象产生之后必须设定成为某个对象的属性等,在启动容器之后,所有的对象都可以直接取用,不用编写任何一行程序代码来产生对象,或是建立对象与对象之间的依赖关系。
换个更直白点的说明方式:容器是一个Java 所编写的程序,原先必须自行编写程序以管理对象关系,现在容器都会自动帮您作好。
常用容器:WebSphere,WebLogic,Resin,Tomcat
----------------------------------
解释二:
容器类
Java容器类包含List、ArrayList、Vector及map、HashTable、HashMap
ArrayList和HashMap是异步的,Vector和HashTable是同步的,所以Vector和HashTable是线程安全的,而 ArrayList和HashMap并不是线程安全的。因为同步需要花费机器时间,所以Vector和HashTable的执行效率要低于 ArrayList和HashMap。
Collection
├List 接口
│├LinkedList 链表
│├ArrayList 顺序结构动态数组类
│└Vector 向量
│ └Stack 栈
└Set
Map
├Hashtable
├HashMap
└WeakHashMap List接口
List是有序的Collection,使用此接口能够精确的控制每个元素插入的位置。用户能够使用索引(元素在List中的位置,类似于数组下标)来访问List中的元素,这类似于Java的数组。
和下面要提到的Set不同,List允许有相同的元素。
除了具有Collection接口必备的iterator()方法外,List还提供一个listIterator()方法,返回一个 ListIterator接口,和标准的Iterator接口相比,ListIterator多了一些add()之类的方法,允许添加,删除,设定元素, 还能向前或向后遍历。
实现List接口的常用类有LinkedList,ArrayList,Vector和Stack。
ArrayList类
ArrayList实现了可变大小的数组。它允许所有元素,包括null。ArrayList没有同步。
size,isEmpty,get,set方法运行时间为常数。但是add方法开销为分摊的常数,添加n个元素需要O(n)的时间。其他的方法运行时间为线性。
每个ArrayList实例都有一个容量(Capacity),即用于存储元素的数组的大小。这个容量可随着不断添加新元素而自动增加,但是增长算法 并没有定义。当需要插入大量元素时,在插入前可以调用ensureCapacity方法来增加ArrayList的容量以提高插入效率。
和LinkedList一样,ArrayList也是非同步的(unsynchronized)。
Map接口
请注意,Map没有继承Collection接口,Map提供key到value的映射。一个Map中不能包含相同的key,每个key只能映射一个 value。Map接口提供3种集合的视图,Map的内容可以被当作一组key集合,一组value集合,或者一组key-value映射。
HashMap类
HashMap和Hashtable类似,不同之处在于HashMap是非同步的,并且允许null,即null value和null key。,但是将HashMap视为Collection时(values()方法可返回Collection),其迭代子操作时间开销和HashMap 的容量成比例。因此,如果迭代操作的性能相当重要的话,不要将HashMap的初始化容量设得过高,或者load factor过低。
Collection接口
Collection是最基本的集合接口,一个Collection代表一组Object,即Collection的元素(Elements)。一些Collection允许相同的元素而另一些不行。一些能排序而另一些不行。Java SDK不提供直接继承自Collection的类,Java SDK提供的类都是继承自Collection的“子接口”如List和Set。
所有实现Collection接口的类都必须提供两个标准的构造函数:无参数的构造函数用于创建一个空的Collection,有一个Collection参数的构造函数用于创建一个新的Collection,这个新的Collection与传入的Collection有相同的元素。后一个构造函数允许用户复制一个Collection。
如何遍历Collection中的每一个元素?不论Collection的实际类型如何,它都支持一个iterator()的方法,该方法返回一个迭代子,使用该迭代子即可逐一访问Collection中每一个元素。典型的用法如下:
Iterator it = collection.iterator(); // 获得一个迭代子
while(it.hasNext()) {
Object obj = it.next(); // 得到下一个元素
}
由Collection接口派生的两个接口是List和Set。
Hashtable类
Hashtable继承Map接口,实现一个key-value映射的哈希表。任何非空(non-null)的对象都可作为key或者value。
添加数据使用put(key, value),取出数据使用get(key),这两个基本操作的时间开销为常数。
Hashtable通过initial capacity和load factor两个参数调整性能。通常缺省的load factor 0.75较好地实现了时间和空间的均衡。增大load factor可以节省空间但相应的查找时间将增大,这会影响像get和put这样的操作。
使用Hashtable的简单示例如下,将1,2,3放到Hashtable中,他们的key分别是”one”,”two”,”three”:
Hashtable numbers = new Hashtable();
numbers.put(“one”, new Integer(1));
numbers.put(“two”, new Integer(2));
numbers.put(“three”, new Integer(3));
要取出一个数,比如2,用相应的key:
Integer n = (Integer)numbers.get(“two”);
System.out.println(“two = ” + n);
由于作为key的对象将通过计算其散列函数来确定与之对应的value的位置,因此任何作为key的对象都必须实现hashCode和equals方法。hashCode和equals方法继承自根类Object,如果你用自定义的类当作key的话,要相当小心,按照散列函数的定义,如果两个对象相同,即obj1.equals(obj2)=true,则它们的hashCode必须相同,但如果两个对象不同,则它们的hashCode不一定不同,如果两个不同对象的hashCode相同,这种现象称为冲突,冲突会导致操作哈希表的时间开销增大,所以尽量定义好的hashCode()方法,能加快哈希表的操作。
如果相同的对象有不同的hashCode,对哈希表的操作会出现意想不到的结果(期待的get方法返回null),要避免这种问题,只需要牢记一条:要同时复写equals方法和hashCode方法,而不要只写其中一个。
Hashtable是同步的。
HashMap类
HashMap和Hashtable类似,不同之处在于HashMap是非同步的,并且允许null,即null value和null key。,但是将HashMap视为Collection时(values()方法可返回Collection),其迭代子操作时间开销和HashMap的容量成比例。因此,如果迭代操作的性能相当重要的话,不要将HashMap的初始化容量设得过高,或者load factor过低。
WeakHashMap类
WeakHashMap是一种改进的HashMap,它对key实行“弱引用”,如果一个key不再被外部所引用,那么该key可以被GC回收。
总结
如果涉及到堆栈,队列等操作,应该考虑用List,对于需要快速插入,删除元素,应该使用LinkedList,如果需要快速随机访问元素,应该使用ArrayList。
如果程序在单线程环境中,或者访问仅仅在一个线程中进行,考虑非同步的类,其效率较高,如果多个线程可能同时操作一个类,应该使用同步的类。
要特别注意对哈希表的操作,作为key的对象要正确复写equals和hashCode方法。
尽量返回接口而非实际的类型,如返回List而非ArrayList,这样如果以后需要将ArrayList换成LinkedList时,客户端代码不用改变。这就是针对抽象编程。
同步性
Vector是同步的。这个类中的一些方法保证了Vector中的对象是线程安全的。而ArrayList则是异步的,因此ArrayList中的对象并不是线程安全的。因为同步的要求会影响执行的效率,所以如果你不需要线程安全的集合那么使用ArrayList是一个很好的选择,这样可以避免由于同步带来的不必要的性能开销。
数据增长
从内部实现机制来讲ArrayList和Vector都是使用数组(Array)来控制集合中的对象。当你向这两种类型中增加元素的时候,如果元素的数目超出了内部数组目前的长度它们都需要扩展内部数组的长度,Vector缺省情况下自动增长原来一倍的数组长度,ArrayList是原来的50%,所以最后你获得的这个集合所占的空间总是比你实际需要的要大。所以如果你要在集合中保存大量的数据那么使用Vector有一些优势,因为你可以通过设置集合的初始化大小来避免不必要的资源开销。
使用模式
在ArrayList和Vector中,从一个指定的位置(通过索引)查找数据或是在集合的末尾增加、移除一个元素所花费的时间是一样的,这个时间我们用O(1)表示。但是,如果在集合的其他位置增加或移除元素那么花费的时间会呈线形增长:O(n-i),其中n代表集合中元素的个数,i代表元素增加或移除元素的索引位置。为什么会这样呢?以为在进行上述操作的时候集合中第i和第i个元素之后的所有元素都要执行位移的操作。这一切意味着什么呢?
这意味着,你只是查找特定位置的元素或只在集合的末端增加、移除元素,那么使用Vector或ArrayList都可以。如果是其他操作,你最好选择其他的集合操作类。比如,LinkList集合类在增加或移除集合中任何位置的元素所花费的时间都是一样的?O(1),但它在索引一个元素的使用缺比较慢-O(i),其中i是索引的位置.使用ArrayList也很容易,因为你可以简单的使用索引来代替创建iterator对象的操作。LinkList也会为每个插入的元素创建对象,所有你要明白它也会带来额外的开销。
最后,在《Practical Java》一书中Peter Haggar建议使用一个简单的数组(Array)来代替Vector或ArrayList。尤其是对于执行效率要求高的程序更应如此。因为使用数组(Array)避免了同步、额外的方法调用和不必要的重新分配空间的操作。
理解集合类
集合类存放于java.util包中。
集合类存放的都是对象的引用,而非对象本身,出于表达上的便利,我们称集合中的对象就是指集合中对象的引用(reference)。
集合类型主要有3种:set(集)、list(列表)和map(映射)。
(1)集
集(set)是最简单的一种集合,它的对象不按特定方式排序,只是简单的把对象加入集合中,就像往口袋里放东西。
对集中成员的访问和操作是通过集中对象的引用进行的,所以集中不能有重复对象。
集也有多种变体,可以实现排序等功能,如TreeSet,它把对象添加到集中的操作将变为按照某种比较规则将其插入到有序的对象序列中。它实现的是SortedSet接口,也就是加入了对象比较的方法。通过对集中的对象迭代,我们可以得到一个升序的对象集合。
(2)列表
列表的主要特征是其对象以线性方式存储,没有特定顺序,只有一个开头和一个结尾,当然,它与根本没有顺序的集是不同的。
列表在数据结构中分别表现为:数组和向量、链表、堆栈、队列。
关于实现列表的集合类,是我们日常工作中经常用到的,将在后边的笔记详细介绍。
(3)映射
映射与集或列表有明显区别,映射中每个项都是成对的。映射中存储的每个对象都有一个相关的关键字(Key)对象,关键字决定了对象在映射中的存储位置,检索对象时必须提供相应的关键字,就像在字典中查单词一样。关键字应该是唯一的。
关键字本身并不能决定对象的存储位置,它需要对过一种散列(hashing)技术来处理,产生一个被称作散列码(hash code)的整数值,散列码通常用作一个偏置量,该偏置量是相对于分配给映射的内存区域起始位置的,由此确定关键字/对象对的存储位置。理想情况下,散列处理应该产生给定范围内均匀分布的值,而且每个关键字应得到不同的散列码。
集合类简介
java.util中共有13个类可用于管理集合对象,它们支持集、列表或映射等集合,以下是这些类的简单介绍
集:
HashSet: 使用HashMap的一个集的实现。虽然集定义成无序,但必须存在某种方法能相当高效地找到一个对象。使用一个HashMap对象实现集的存储和检索操作是在固定时间内实现的.
TreeSet: 在集中以升序对对象排序的集的实现。这意味着从一个TreeSet对象获得第一个迭代器将按升序提供对象。TreeSet类使用了一个TreeMap.
列表:
Vector: 实现一个类似数组一样的表,自动增加容量来容纳你所需的元素。使用下标存储和检索对象就象在一个标准的数组中一样。你也可以用一个迭代器从一个Vector中检索对象。Vector是唯一的同步容器类??当两个或多个线程同时访问时也是性能良好的。
Stack: 这个类从Vector派生而来,并且增加了方法实现栈??一种后进先出的存储结构。
LinkedList: 实现一个链表。由这个类定义的链表也可以像栈或队列一样被使用。
ArrayList: 实现一个数组,它的规模可变并且能像链表一样被访问。它提供的功能类似Vector类但不同步。
映射:
HashTable: 实现一个映象,所有的键必须非空。为了能高效的工作,定义键的类必须实现hashcode()方法和equal()方法。这个类是前面java实现的一个继承,并且通常能在实现映象的其他类中更好的使用。
HashMap: 实现一个映象,允许存储空对象,而且允许键是空(由于键必须是唯一的,当然只能有一个)。
WeakHashMap: 实现这样一个映象:通常如果一个键对一个对象而言不再被引用,键/对象对将被舍弃。这与HashMap形成对照,映象中的键维持键/对象对的生命周期,尽管使用映象的程序不再有对键的引用,并且因此不能检索对象。
TreeMap: 实现这样一个映象,对象是按键升序排列的。
Set和List都是由公共接口Collection扩展而来,所以它们都可以使用一个类型为Collection的变量来引用。这就意味着任何列表或集构成的集合都可以用这种方式引用,只有映射类除外(但也不是完全排除在外,因为可以从映射获得一个列表。)所以说,把一个列表或集传递给方法的标准途径是使用Collection类型的参数。
另外,站长团上有产品团购,便宜有保证
求java 单链表基本操作的实现
/*
注意:链表的结点数量用size表示,结点的位置为0~size-1
*/
import java.util.Scanner;
public class Test7 {
public static void main(String[] args) {
try{
LinkList list = new LinkList();
Integer value;
int pos = 0;
Scanner input = new Scanner(System.in);
String choice = null;
//测试A
while(true){
System.out.print("请输入待插入结点的值(x或X退出):");
choice = input.next();
if(choice.toUpperCase().equals("X")){
break;
}
value = Integer.valueOf(choice);
if(list.addAt(pos, value) == true){
System.out.println("插入值为 " + value + " 的结点到当前链表成功!");
pos++;
}
else{
System.out.println("插入结点失败!");
}
}
System.out.print("当前链表所有结点:");
list.listAll();
//测试B
while(true){
System.out.print("请输入待查询结点的值(x或X退出):");
choice = input.next();
if(choice.toUpperCase().equals("X")){
break;
}
value = Integer.valueOf(choice);
pos = list.findByValue(value);
if(pos == -1){
System.out.println("当前链表中不存在值为 " + value + " 的结点");
}
else{
System.out.println("值为 " + value + " 的结点在当前链表中的位置为 " + pos);
}
}
//测试C
while(true){
System.out.print("请输入待删除结点的位置[0~" + (list.getSize()-1) + "](x或X退出):");
choice = input.next();
if(choice.toUpperCase().equals("X")){
break;
}
pos = Integer.valueOf(choice);
if(list.removeAt(pos) == true){
System.out.println("删除当前链表中 " + pos + " 位置的结点成功!");
}
else{
System.out.println("删除结点失败!");
}
}
System.out.print("当前链表所有结点:");
list.listAll();
}
catch(Exception e){
e.printStackTrace();
}
}
}
/**
* 链表结点类
*/
class Node{
private Object data; //链表结点的数据域
private Node next; //链表结点的指针域,指向直接后继结点
public Node(){
data = null;
next = null;
}
public Node(Object data, Node next){
this.data = data;
this.next = next;
}
public Object getData(){
return this.data;
}
public void setData(Object data){
this.data = data;
}
public Node getNext(){
return this.next;
}
public void setNext(Node next){
this.next = next;
}
}
/**
* 链表类
*/
class LinkList{
private Node head = null; //头结点指针
private int size = 0;
public LinkList(){
head = new Node();
size = 0;
}
//在i位置插入元素elem
public boolean addAt(int i, Object elem) {
if(i 0 || i size){
return false;
}
Node pre,curr;
int pos;
for(pre=head; i0 pre.getNext()!=null; i--,pre=pre.getNext());
curr = new Node(elem, pre.getNext());
pre.setNext(curr);
size++;
return true;
}
//删除i位置的元素
public boolean removeAt(int i) {
if(i 0 || i = size){
return false;
}
Node pre,curr;
for(pre=head; i0 pre.getNext()!=null; i--,pre=pre.getNext());
curr = pre.getNext();
pre.setNext(curr.getNext());
size--;
return true;
}
//根据值value查询结点是否存在,若存在返回位置,否则返回-1
public int findByValue(Object value){
Node curr;
int pos;
for(pos=0,curr=head.getNext(); curr!=null; pos++,curr=curr.getNext()){
if(curr.getData().toString().equals(value.toString())){
break;
}
}
if(curr==null){
return -1;
}
return pos;
//return (curr!=null ? pos : -1);
}
public int getSize(){
return size;
}
public boolean isEmpty(){
return (size==0);
}
public void listAll(){
for(Node curr=head.getNext(); curr!=null; curr=curr.getNext()){
System.out.print(curr.getData() + "\t");
}
System.out.println();
}
}
java 链表的输出问题
几位的回答都比较清楚了,我想另外说点问题
你本就不应该加入‘表尾’这个属性,在数据结构中链表的特点就是能用一个地址带一个长串数据链的,不用这个属性的话思路会更加清晰。我也用java模拟过一些基本数据结构:
public class MyNodeT {
public T value;
public MyNodeT next;
public MyNode() {
}
public MyNode(T value) {
this.value = value;
}
public MyNode(MyNodeT t) {
this.value = t.value;
this.next = t.next;
}
public void connect(MyNodeT t){
this.next = t;
}
@Override
public String toString() {
return null==value?"":value+"-";
}
}
在这个节点定义的基础上的链表定义:
public class MyLinkListT{
public MyNodeT next;
public MyLinkList() {
this.next = new MyNodeT();
}
public MyLinkList(T[] tList) {
if(tList.length==0)return;
next = new MyNodeT(tList[0]);
MyNodeT temp = next;
for (int i = 1; i tList.length; i++) {
temp.connect(new MyNodeT(tList[i]));
temp = temp.next;
}
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
MyNodeT t = next;
while (null != t) {
sb.append(t);
t = t.next;
}
return sb.toString();
}
}
然后是相关的操作类:
public class LinkListAction {
MyLinkListComparable list;
public LinkListAction(MyLinkListComparable list) {
this.list = list;
}
/**
* 头插法建立单链表(数组)
* */
public void createFromHead(Comparable...objects){
MyNodeComparable start;
for (int i = 0; i objects.length; i++) {
start = new MyNodeComparable(objects[i]);
start.next = list.next;
list.next = start;
}
}
/**
* 尾插法建立单链表(数组)
* */
public void createFromTail(Comparable...objects){
MyNodeComparable start;
MyNodeComparable end = list.next;
for (int i = 0; i objects.length; i++) {
start = new MyNodeComparable(objects[i]);
end.next = start;
end = start;
}
end.next = null;
}
/**
* 在单链表中查找第i个结点
* */
public MyNodeComparable get(int i){
if(i 0)return null;
MyNodeComparable node = list.next;
int index = 0;
while (node != null index i) {
node = node.next;
index++;
}
return node;
}
/**
* 在单链表中的按值查找
* */
public MyNodeComparable locate(Comparable obj){
if(null == obj)return new MyNodeComparable();
MyNodeComparable node = list.next;
while (node != null !obj.equals(node.value)) {
node = node.next;
}
return node;
}
/**
* 求单链表的长度
* */
public int getLength(){
int length = 0;
MyNodeComparable node = list.next;
while(null != (node = node.next)){
length++;
}
return length;
}
/**
* 单链表的插入操作(按位置)
* */
public void insert(Comparable obj,int location){
int length = 0;
MyNodeComparable node = list.next;
while(node!=null location != length++){node = node.next;}
if(null == node)throw new RuntimeException("插入位置有误!");
MyNodeComparable inserter = new MyNodeComparable(obj);
inserter.next = node.next;
node.next = inserter;
}
/**
* 删除数据
* */
public Comparable delete(int i){
int length = 0;
MyNodeComparable node = list.next;
while(node!=null i != length++){node = node.next;}
if(null == node)throw new RuntimeException("删除位置有误!");
Comparable o = node.next.value;
node.next = node.next.next;
return o;
}
/**
* 合并两个有序的单链表
* */
public static MyLinkListComparable mergeLinkList(MyLinkListComparable la,MyLinkListComparable lb){
MyLinkListComparable lc = new MyLinkListComparable();
MyNodeComparable pc = lc.next;
MyNodeComparable pa = la.next.next;
MyNodeComparable pb = lb.next.next;
while(null != pa || null != pb){
if(null == pa){
pc.next = pb;
break;
}
if(null == pb){
pc.next = pa;
break;
}
if(pa.value.compareTo(pb.value) = 0){
pc.next = pa;
pa = pa.next;
}
else {
pc.next = pb;
pb = pb.next;
}
pc = pc.next;
}
return lc;
}
@Override
public String toString() {
return list.toString();
}
public static void main(String[] args) {
MyLinkListComparable list1 = new MyLinkListComparable();
MyLinkListComparable list2 = new MyLinkListComparable();
LinkListAction lla = new LinkListAction(list1);
// lla.createFromHead(1,3,4,6,8,10);
lla.createFromTail(1,3,4,6,8,10);
LinkListAction llb = new LinkListAction(list2);
llb.createFromTail(2,5,7,9,11);
System.out.println(lla);
System.out.println(llb);
// System.out.println(lla.locate(7));
// System.out.println(lla.getLength());
//
// lla.insert(20, 6);
// System.out.println(lla);
// System.out.println(lla.delete(4));
System.out.println(LinkListAction.mergeLinkList(lla.list, llb.list));
System.out.println(lla);
System.out.println(llb);
}
}
我还写了一些其他的简单数据结构,感兴趣的话,你可以Hi我一下,呵呵。
圣诞快乐!
链表的基本操作java的介绍就聊到这里吧,感谢你花时间阅读本站内容,更多关于链表的基本操作实验总结、链表的基本操作java的信息别忘了在本站进行查找喔。
发布于:2022-11-23,除非注明,否则均为
原创文章,转载请注明出处。