用java如何创建一个单链表和双链表

单向链表

单向链表就是通过每个结点的指针指向下一个结点从而链接起来的结构。

单向链表的初始化：这里我所讲的链表都是头结点不参与计算的，也就是说第一个结点都是头结点后面的第一个结点。所以我要先申明一点，这里我把链表的初始化放在了构造函数部分，然后析构函数负责释放头结点的内存。

单向链表的创建过程：链表的创建就是添加结点到链表的最后，开始是添加一个结点到head结点后面，然后添加一个结点到上次添加的结点后面，每次新建的结点的指针总是指向NULL指针。从上面的示意图可以看出，我们需要一个辅助指针一直指向最后一个结点，这个辅助结点就是为了让每次添加的结点都放置在最后一个位置。

单向链表插入结点过程：源代码中的的插入结点函数我设置了一个指定位置，就是在指定位置插入结点。首先，通过位置变量position让ptemp结点移动到要插入位置的前一个位置，然后接下来的过程就是和创建链表的过程是一样的，把新建的结点添加到ptemp的后面。这里变量position可以从1到链表长度加1，意思就是如果不算头结点的话有3个结点，那你的position变量就可以从1到4，这是因为ptemp指针可以到第3个结点的位置，所以新建结点的位置就可以到4了。

单向链表删除结点过程：源代码中的删除结点函数也有一个指定位置变量，为了删除指定位置的结点。和插入结点一样通过变量position把ptemp移动到要删除结点的前一个位置，然后让ptemp结点中的指针指向要删除结点后面的一个结点，也就是ptemp结点的下一个的下一个结点，虽然这个结点可能为空，但是程序还是正常运行。但是这里和插入结点不同的是变量position只能从1到链表的长度，是因为ptemp移动到最后一个结点的时候，它的下一个结点为空，所以不不需要参与删除了。

双向链表

1听名字可能就能猜到双向链表就是链表结点包含两个指针，一个指针是指向下一个结点的，另一个指针当然就是指向上一个结点的。

2双向链表的初始化：由于这里的链表头结点不参与计算，所以头结点的pPre指针是一直指向NULL指针的。

3双向链表的创建过程：由于双向链表的每个结点包含两个指针那么这个时候我们就要小心处理好每一个指针的指向，要不然会有很多意想不到的错误。同样的，和单向链表的创建过程一样，需要一个辅助指针来指向最后一个结点，然后每新建一个结点，这个结点的pNext指针都是指向NULL指针的，pPre指针指向上一个结点（这是和单向链表不同的地方），然后让上一个指针的pNext指向新建的结点，这样整个链表就连接起来了。

4双向链表插入结点过程：知道了双向链表的创建过程，那么插入结点的过程就大同小异 了，有一点需要特别注意的就是这里的变量position范围也是从1到链表长度加1，但是如果待插入的位置是最后一个位置的话，情况就不同了，看到下面的图我们可以很好的理解，因为没新建一个结点的时候都需要处理两个指针，而且新建结点的下一个结点的pPre指针就需要指向这个新建的结点，但是有可能这个新建的结点可能就已经是最后一个结点了，那么这个时候再执行

ptemp->pNext->pPre = pnew;

这条指令的时候就会报错了，因为ptemp->pNext已经是个NULL指针了，那空指针哪里还有pPre呢。因此在程序中要进行一次判断，看看结点是否是最后一个结点。

5双向链表删除结点的过程：要注意的问题和插入结点一样，看看这个结点是否为NULL。这里就不重复了。

import javautilArrays;

import javautilLinkedList;

import javautilScanner;

import javautilTreeSet;

public class Day16_LinkedList {

static Scanner sc=new Scanner(Systemin);

public static void main(String[] args) {

Integer[] arr= {1,2,3,0,5,6,7,8,0,0,0,1,2,3};

LinkedList<Integer> lin=new LinkedList<>();

linaddAll(ArraysasList(arr));

while(true) {

sop(ArraystoString(arr));

sop("输入想查找的值:");

int value=scnextInt();

lookUp(lin,value);

}

}

public static void lookUp(LinkedList<> list,int key) {

LinkedList<> tem=(LinkedList<>) listclone();

TreeSet<Integer> ts=new TreeSet<>();

int count=0;

while(true) {

int x=temindexOf(key);

int y=temlastIndexOf(key);

if(x<0||y<0) {

break;

}

if(x!=y) {

count+=2;

temremoveFirstOccurrence(key);

temremoveLastOccurrence(key);

tsadd(x);

tsadd(y);

}else {

count++;

tsadd(y);

break;

}

}

if(count<1) {

sop("目标不存在\r\n");

return;

}

sop("目标索引位置是:"+ts+"\t该值共:"+tssize()+" 个\r\n");

}

private static void sop(String str) {

Systemoutprintln(str);

}

}

重复的也能全部找出来!

//如果感兴趣的话，可以把下面的改成泛型的也就是这样的
//一个学生的类
public class Stu(){
String name;
int age;
public Stu(String name,int age){
thisname=name;
thisage=age;
}
}
//创建两个学生的对像
Stu stu1=new Stu("weiwie",24);
Stu stu2=new Stu("xiaoqiang",25);
//创建集合类,存放的是Stu对像,这样的声明只能存Stu对像
List <Stu> list=new ArrayList<Stu>();
//存数据
listadd(stu1);
listadd(stu2);
//遍历
for(int i=0;i<listsize();i++){
//向下转型方便了,取出来的就是Stu对像
Stu stu=listget(i);
}
List list=new ArrayList();
listadd("对像");
遍历
for(int i=0;i<listsize();i++){
//需要强转
String str=(String)listget(i);
得到你存放的数据
}
Map map=new HashMap();
//存值
mapput("one","对像");
//取值
String str=(String)mapget("one");
Set set=new HashSet();
//存值
setadd("对像");
//需要用这个对像遍历
Iterator iter=setiterator();
while(iterhasNext()){
//取值
String Str=(String)iternext();
}

因为你AirLineInformation A = new AirLineInformation();
这个引用A没变过啊
不管你加几次都是加的这个A，而A表示的数据就是你最后修改后的数据，在list里的01保存的引用地址都是A，而A指向的对象被你不停的修改，明白了没
建议每次都建立一个AirLineInformation对象，这也是正常逻辑上的，不知道为什么你想就用一个对象

链表是一种重要的数据结构 在程序设计中占有很重要的地位 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 = ; public void deleteAll() / 清空整个链表 / { Head = null; Tail = null; Pointer = null; Length = ; } public void reset() / 链表复位 使第一个结点成为当前结点 / { Pointer = null; } public boolean isEmpty( ) / 判断链表是否为空 / { return( Length == ); } public boolean isEnd() / 判断当前结点是否为最后一个结点 / { if ( Length == ) throw new java lang NullPointerException(); else if ( Length == ) return true; else return( cursor() == Tail ); } public Object nextNode() / 返回当前结点的下一个结点的值 并使其成为当前结点 / { if ( Length == ) throw new java util NoSuchElementException(); else if ( Length == ) 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 == ) { 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 == ) throw new java util NoSuchElementException(); else if ( Length == ) { 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 = ; i <= 10; i++ ) ainsert( new Integer( i ) ); Systemoutprintln( acurrentNode() ); while ( !aisEnd() ) Systemoutprintln( anextNode() ); areset(); while ( !aisEnd() ) { aremove(); } aremove(); areset(); if ( aisEmpty() ) Systemoutprintln("There is no Node in List \n"); Systeminprintln( " You can press return to quit\n" ); try { Systeminread(); // 确保用户看清程序运行结果 } catch( IOException e ) {} } } class Node / 构成链表的结点定义 / { Object data; Node next; Node( Object d ) { data = d; next = null; } } 读者还可以根据实际需要定义新的方法来对链表进行 *** 作。wInGwiTCom双向链表可以用类似的方法实现只是结点的类增加了一个指向前趋结点的指针。 我们可以用这样的代码来实现： class Node { Object data; Node next; Node previous; Node ( Object d ) { data = d; next = null; previous = null; } } 当然双向链表基本 *** 作的实现略有不同，这里就不再详述了。链表和双向链表的实现方法，也可以用在堆栈和队列的实现中，这里就不再多写了，有兴趣的读者可以将List类的代码稍加改动即可。 lishixinzhi/Article/program/Java/Javascript/201311/25266

一个二维数组可以看成一个一维数组，每个元素存储一个一维数组首地址的引用，这个没问题吧！
也就是说对于a[][]，直接用b[][]=a,或者b[][]=aclone() 都只是复制了一个引用(包括上面的arraycopy等方法)，无法保证数据独立性，就是说a数组值改变会影响到b，反之亦然，这就是浅层复制。
如果二维数组存放类型为基本类型，则只需要b的每一行进行复制(Objectclone()可以保证对基本类型做深层复制api上有写):
b[][]=aclone();//先利用浅层复制分配新的引用存放地址
for(int i=0;i<alength;i++){
b[i]=a[i]clone();//a[i]指向数组的内容为基本类型，可以深层复制生成新引用对象
}
如果二维数组表示的是引用类型，则要对每一个元素调用clone()，并且保证所表示的引用类型遵循clone()复写原则。
b[][]=aclone();//先利用浅层复制分配新的引用存放地址
for(int i=0;i<alength;i++){
for(int j=0;j<a[0]length;j++){
b[i][j]=a[i][j]clone()//为每个元素进行深层复制
}
}
以上是规范写法，实现方法有很多，但一定要记住，单纯的对引用的COPY是没有意义的，编程中要避免。

---