双向
链表:就是有双向
指针,即双向的链域。\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)链表类,结点类(链表类的内部类),在main()方法创建一条链表类对象,通过方法逐步创建结点类,通过引用链接起来成为链表。2)结点类包含数据和对下个结点的引用,以及可以对数据赋值的构造函数。3)链表类的构造方法,只构造出不含数据的头结点。(外部类可以直接对内部类的私有成员进行访问,这样就可以直接修改引用)class Node {
Object data
Node next//申明类Node类的对象叫Next
public Node(Object data) { //类Node的构造函数
setData(data)
}
public void setData(Object data) {
this.data = data
}
public Object getData() {
return data
}
}
class Link {
Node head//申明一个Node类的一个对象 head
int size = 0
public void add(Object data) {
Node n = new Node(data)//调用Node类的构造函数
链表是一种重要的数据结构,在程序设计中占有很重要的地位。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=1i<=10i++)
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类
的代码稍加改动即可。