![R和Rstudio终端显示语言的更改[Windows]](/aiimages/R%E5%92%8CRstudio%E7%BB%88%E7%AB%AF%E6%98%BE%E7%A4%BA%E8%AF%AD%E8%A8%80%E7%9A%84%E6%9B%B4%E6%94%B9%5BWindows%5D.png)
![python中a[1][2]是什么意思](/aiimages/python%E4%B8%ADa%5B1%5D%5B2%5D%E6%98%AF%E4%BB%80%E4%B9%88%E6%84%8F%E6%80%9D.png)
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类的代码稍加改动即可。
希望对你有帮助。
定义接口：//Deque.java
package dsa//根据自己的程序位置不同
public interface Deque {
public int getSize()//返回队列中元素数目
public boolean isEmpty()//判断队列是否为空
public Object first() throws ExceptionQueueEmpty//取首元素（但不删除）
public Object last() throws ExceptionQueueEmpty//取末元素（但不删除）
public void insertFirst(Object obj)//将新元素作为首元素插入
public void insertLast(Object obj)//将新元素作为末元素插入
public Object removeFirst() throws ExceptionQueueEmpty//删除首元素
public Object removeLast() throws ExceptionQueueEmpty//删除末元素
public void Traversal()//遍历
}
双向链表实现：
//Deque_DLNode.java
/*
* 基于双向链表实现双端队列结构
*/
package dsa
public class Deque_DLNode implements Deque {
protected DLNode header//指向头节点（哨兵）
protected DLNode trailer//指向尾节点（哨兵）
protected int size//队列中元素的数目
//构造函数
public Deque_DLNode() {
header = new DLNode()
trailer = new DLNode()
header.setNext(trailer)
trailer.setPrev(header)
size = 0
}
//返回队列中元素数目
public int getSize()
{ return size}
//判断队列是否为空
public boolean isEmpty()
{ return (0 == size) ? true : false}
//取首元素（但不删除）
public Object first() throws ExceptionQueueEmpty {
if (isEmpty())
throw new ExceptionQueueEmpty("意外：双端队列为空")
return header.getNext().getElem()
}
//取末元素（但不删除）
public Object last() throws ExceptionQueueEmpty {
if (isEmpty())
throw new ExceptionQueueEmpty("意外：双端队列为空")
return trailer.getPrev().getElem()
}
//在队列前端插入新节点
public void insertFirst(Object obj) {
DLNode second = header.getNext()
DLNode first = new DLNode(obj, header, second)
second.setPrev(first)
header.setNext(first)
size++
}
//在队列后端插入新节点
public void insertLast(Object obj) {
DLNode second = trailer.getPrev()
DLNode first = new DLNode(obj, second, trailer)
second.setNext(first)
trailer.setPrev(first)
size++
}
//删除首节点
public Object removeFirst() throws ExceptionQueueEmpty {
if (isEmpty())
throw new ExceptionQueueEmpty("意外：双端队列为空")
DLNode first = header.getNext()
DLNode second = first.getNext()
Object obj = first.getElem()
header.setNext(second)
second.setPrev(header)
size--
return(obj)
}
//删除末节点
public Object removeLast() throws ExceptionQueueEmpty {
if (isEmpty())
throw new ExceptionQueueEmpty("意外：双端队列为空")
DLNode first = trailer.getPrev()
DLNode second = first.getPrev()
Object obj = first.getElem()
trailer.setPrev(second)
second.setNext(trailer)
size--
return(obj)
}
//遍历
public void Traversal() {
DLNode p = header.getNext()
while (p != trailer) {
System.out.print(p.getElem()+" ")
p = p.getNext()
}
System.out.println()
}
}
