javaListNode链表就是用Java自定义实现的链表结构。
链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点组成，结点可以在运行时动态生成。
双向链表：就是有双向指针，即双向的链域。\x0d\x0a链结点的结构：\x0d\x0a┌────┬────┬────────┐\x0d\x0a│ data │ next │ previous │\x0d\x0a└────┴────┴────────┘\x0d\x0a双向链表不必是双端链表(持有对最后一个链结点的引用)，双端链表插入时是双向的。\x0d\x0a有两条链：一条从头到尾，一条从尾到头，删除遍历时也是双向的。\x0d\x0a/**\x0d\x0a * 双向链表\x0d\x0a */\x0d\x0apublic class DoublyLinkedList {\x0d\x0aprivate Link head //首结点\x0d\x0aprivate Link rear //尾部指针\x0d\x0apublic DoublyLinkedList() { }\x0d\x0apublic T peekHead() {\x0d\x0aif (head != null) {\x0d\x0areturn head.data\x0d\x0a}\x0d\x0areturn null\x0d\x0a}\x0d\x0apublic boolean isEmpty() {\x0d\x0areturn head == null\x0d\x0a}\x0d\x0apublic void insertFirst(T data) {// 插入 到 链头\x0d\x0aLink newLink = new Link(data)\x0d\x0aif (isEmpty()) {//为空时，第1次插入的新结点为尾结点\x0d\x0arear = newLink\x0d\x0a} else {\x0d\x0ahead.previous = newLink//旧头结点的上结点等于新结点\x0d\x0a}\x0d\x0anewLink.next = head//新结点的下结点旧头结点\x0d\x0ahead = newLink//赋值后，头结点的下结点是旧头结点，上结点null\x0d\x0a}\x0d\x0apublic void insertLast(T data) {//在链尾 插入\x0d\x0aLink newLink = new Link(data)\x0d\x0aif (isEmpty()) {\x0d\x0ahead = newLink\x0d\x0a} else {\x0d\x0arear.next = newLink\x0d\x0a}\x0d\x0anewLink.previous = rear\x0d\x0arear = newLink//赋值后，尾结点的上结点是旧尾结点，下结点null\x0d\x0a}\x0d\x0apublic T deleteHead() {//删除 链头\x0d\x0aif (isEmpty()) return null\x0d\x0aLink temp = head\x0d\x0ahead = head.next//变更首结点，为下一结点\x0d\x0aif (head != null) {\x0d\x0ahead.previous = null\x0d\x0a} else {\x0d\x0arear = null\x0d\x0a}\x0d\x0areturn temp.data\x0d\x0a}\x0d\x0apublic T deleteRear() {//删除 链尾\x0d\x0aif (isEmpty()) return null\x0d\x0aLink temp = rear\x0d\x0arear = rear.previous//变更尾结点，为上一结点\x0d\x0aif (rear != null) {\x0d\x0arear.next = null\x0d\x0a} else {\x0d\x0ahead = null\x0d\x0a}\x0d\x0areturn temp.data\x0d\x0a}\x0d\x0apublic T find(T t) {//从头到尾find\x0d\x0aif (isEmpty()) {\x0d\x0areturn null\x0d\x0a}\x0d\x0aLink find = head\x0d\x0awhile (find != null) {\x0d\x0aif (!find.data.equals(t)) {\x0d\x0afind = find.next\x0d\x0a} else {\x0d\x0abreak\x0d\x0a}\x0d\x0a}\x0d\x0aif (find == null) {\x0d\x0areturn null\x0d\x0a}\x0d\x0areturn find.data\x0d\x0a}\x0d\x0apublic T delete(T t) {\x0d\x0aif (isEmpty()) {\x0d\x0areturn null\x0d\x0a}\x0d\x0aLink current = head\x0d\x0awhile (!current.data.equals(t)) {\x0d\x0acurrent = current.next\x0d\x0aif (current == null) {\x0d\x0areturn null\x0d\x0a}\x0d\x0a}\x0d\x0aif (current == head) {\x0d\x0ahead = head.next\x0d\x0aif (head != null) {\x0d\x0ahead.previous = null\x0d\x0a}\x0d\x0a} else if (current == rear) {\x0d\x0arear = rear.previous\x0d\x0aif (rear != null) {\x0d\x0arear.next = null\x0d\x0a}\x0d\x0a} else {\x0d\x0a//中间的非两端的结点，要移除current\x0d\x0acurrent.next.previous = current.previous\x0d\x0acurrent.previous.next = current.next\x0d\x0a}\x0d\x0areturn current.data\x0d\x0a}\x0d\x0apublic boolean insertAfter(T key, T data) {//插入在key之后, key不存在return false\x0d\x0aif (isEmpty()) {\x0d\x0areturn false\x0d\x0a}\x0d\x0aLink current = head\x0d\x0awhile (!current.data.equals(key)) {\x0d\x0acurrent = current.next\x0d\x0aif (current == null) {\x0d\x0areturn false\x0d\x0a}\x0d\x0a}\x0d\x0aLink newLink = new Link(data)\x0d\x0aif (current == rear) {\x0d\x0arear = newLink\x0d\x0a} else {\x0d\x0anewLink.next = current.next\x0d\x0acurrent.next.previous = newLink\x0d\x0a}\x0d\x0acurrent.next = newLink\x0d\x0anewLink.previous = current\x0d\x0areturn true\x0d\x0a}\x0d\x0apublic void displayList4Head() {//从头开始遍历\x0d\x0aSystem.out.println("List (first-->last):")\x0d\x0aLink current = head\x0d\x0awhile (current != null) {\x0d\x0acurrent.displayLink()\x0d\x0acurrent = current.next\x0d\x0a}\x0d\x0a}\x0d\x0apublic void displayList4Rear() {//从尾开始遍历\x0d\x0aSystem.out.println("List (last-->first):")\x0d\x0aLink current = rear\x0d\x0awhile (current != null) {\x0d\x0acurrent.displayLink()\x0d\x0acurrent = current.previous\x0d\x0a}\x0d\x0a}\x0d\x0a\x0d\x0aclass Link {//链结点\x0d\x0aT data//数据域\x0d\x0aLink next//后继指针，结点 链域\x0d\x0aLink previous//前驱指针，结点 链域\x0d\x0aLink(T data) {\x0d\x0athis.data = data\x0d\x0a}\x0d\x0avoid displayLink() {\x0d\x0aSystem.out.println("the data is " + data.toString())\x0d\x0a}\x0d\x0a}\x0d\x0apublic static void main(String[] args) {\x0d\x0aDoublyLinkedList list = new DoublyLinkedList()\x0d\x0alist.insertLast(1)\x0d\x0alist.insertFirst(2)\x0d\x0alist.insertLast(3)\x0d\x0alist.insertFirst(4)\x0d\x0alist.insertLast(5)\x0d\x0alist.displayList4Head()\x0d\x0aInteger deleteHead = list.deleteHead()\x0d\x0aSystem.out.println("deleteHead:" + deleteHead)\x0d\x0alist.displayList4Head()\x0d\x0aInteger deleteRear = list.deleteRear()\x0d\x0aSystem.out.println("deleteRear:" + deleteRear)\x0d\x0alist.displayList4Rear()\x0d\x0aSystem.out.println("find:" + list.find(6))\x0d\x0aSystem.out.println("find:" + list.find(3))\x0d\x0aSystem.out.println("delete find:" + list.delete(6))\x0d\x0aSystem.out.println("delete find:" + list.delete(1))\x0d\x0alist.displayList4Head()\x0d\x0aSystem.out.println("----在指定key后插入----")\x0d\x0alist.insertAfter(2, 8)\x0d\x0alist.insertAfter(2, 9)\x0d\x0alist.insertAfter(9, 10)\x0d\x0alist.displayList4Head()\x0d\x0a}\x0d\x0a}1.先定义一个节点类package com.buren
public class IntNode {
//定义一个节点类
int
info
//定义属性，节点中的值
IntNode next
//定义指向下一个节点的属性
public IntNode(int
i){ //构造一个next为空的节点
this(i,null)
}
public IntNode(int i,IntNode
n){ //构造值为i指向n的节点
info=i
next=n
}
}
2.再定义一个链表类，这是主要部分
package com.buren
public class IntSLList {
private IntNode head,tail
//定义指向头结点和尾结点的指针，
//如果大家看着这个不像指针的话，那就需要对指针有更深刻的了解
public
IntSLList(){
//定义一个空节点
head=tail=null
}
public boolean
isEmpty(){
//判断节点是否为空
return
head==null
//这行代码看起来似乎很神奇，其实真的很神奇，偶是服了
}
public void addToHead(int el){
//将el插入到头结点前
head=new
IntNode(el,head)
//将节点插入到头结点前，作为新的投节点
if(head==tail){
//给空链表插入节点时
tail=head
//头结点和尾结点指向同一个节点
}
}
public void addToTail(int
el){
//向链表的尾部增加结点
if(!isEmpty()){
//判断链表是否为空
tail.next=new
IntNode(el)
//新建立一个值为el的节点，将链表的尾结点指向新节点
tail=tail.next
//更新尾指针的指向
}else{
head=tail=new
IntNode(el)
//如果链表为空，新建立一个节点，将头尾指针同时指向这个节点
}
}
public int
deleteFromHead(){
//删除头结点，将节点信息返回
int
el=head.info
//取出节点信息
if(head==tail){
//如果链表中只有一个节点
head=tail=null
//删除这一个节点
}else{
head=head.next
//如果链表中不止一个节点，将头结点的下一个节点作为头结点
}
return
el
//返回原头结点的值
}
public int
deleteFromTail(){
//删除尾结点，返回尾结点的信息
int
el=tail.info
//取出尾结点的值
if(head==tail){
// 如果链表中只有一个节点
head=tail=null
//删除这个节点
}else{
IntNode
temp
//定义中间变量
for(temp=headtemp.next!=tailtemp=temp.next)
//找出尾结点的前一个节点，注意最后的分号，
//这个for循环是没有循环体的，目的在于找出尾结点的前一个节点
//在整个程序中用了很多次这样的写法，相当经典啊
tail=temp
//将找出来的节点作为尾结点，删除原来的尾结点
tail.next=null
//将新尾结点的指向设为空
}
return
el
//返回原尾结点的信息
}
public void
printAll(){
//打印链表中所有节点的信息
if(isEmpty()){
//如果链表为空
System.out.println("This
list is
empty!")
//输出提示信息
return
//返回到调用的地方
}
if(head==tail){
//当链表中只有一个节点时
System.out.println(head.info)
//输出这个节点的信息，就是头结点的信息
return
}
IntNode
temp
//定义一个中间变量
for(temp=headtemp!=nulltemp=temp.next){
//遍历整个链表
System.out.print(temp.info+"
")
//输出每个节点的信息
}
System.out.println()
//输出一个换行，可以没有这一行
}
public boolean isInList(int
el){
//判断el是否存在于链表中
IntNode
temp
//定义一个中间变量
for(temp=headtemp!=null
&&
temp.info!=eltemp=temp.next)
//将el找出来，注意最后的分
return
temp!=null
// 如果存在返回true，否则返回flase，这两行代码很有思想
}
public void delete(int
el){
//删除链表中值为el的节点
if(head.info==el
&&
head==tail){
//如果只有一个节点，并且节点的值为el
head=tail=null
//删除这个节点
}else
if(head.info==el){
// 不止一个节点，而头结点的值就是el
head=head.next
//删除头结点
}else{
IntNode
pred,temp
//定义两个中间变量
for(pred=head,temp=head.nexttemp.info!=el
&&
temp.next!=nullpred=pred.next,temp=temp.next)
//跟上面的类似，自己琢磨吧，也是要注意最后的分号
pred.next=temp.next
//将temp指向的节点删除，最好画一个链表的图，有助于理解
if(temp==tail){
//如果temp指向的节点是尾结点
tail=pred
//将pred指向的节点设为尾结点，
}
}
}
//下面这个方法是在链表中值为el1的节点前面插入一个值为el2的节点，
//用类似的思想可以再写一个在链表中值为el1的节点后面插入一个值为el2的节点
public boolean insertToList(int el1,int
el2){
//定义一个插入节点的方法，插入成功返回true，否则返回false
IntNode
pred,temp //定义两个中间变量
if(isEmpty()){
//判断链表是否为空
return
false
//如果链表为空就直接返回false
}
if(head.info==el1
&&
head==tail){
//如果链表中只有一个节点，并且这个节点的值是el1
head=new
IntNode(el2,head)
//新建立一个节点
return
true
}else if(head.info==el1){
IntNode t=new
IntNode(el2)
t.next=head
head=t
return
true
}else{
for(pred=head,temp=head.nexttemp!=null
&&
temp.info!=el1pred=pred.next,temp=temp.next)
if(temp!=null){
IntNode
a=new IntNode(el2)
pred.next=a
a.next=temp
return
true
}else{
System.out.println(el1+"
NOT EXEISTS!")
return
false
}
}
}
3.下面是测试代码
public static void main(String[] args){
IntSLList test=new
IntSLList()
//test.addToHead(7)
test.addToTail(7)
System.out.println(test.insertToList(7,5))
test.printAll()
System.out.println(test.isInList(123))
}
}
