实现一个链表有删除，添加 *** 作

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.out.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

}

}

①双链表的前插 *** 作

void

DInsertBefore(DListNode

*p,DataType

x)

{//在带头结点的双链表中，将值为x的新结点插入*p之前，设p≠NULL

DListNode

*s=malloc(sizeof(DListNode))//①

s->data=x//②

s->prior=p->prior//③

s->next=p//④

p->prior->next=s//⑤

p->prior=s//⑥

}

②双链表上删除结点*p自身的 *** 作

void

DDeleteNode(DListNode

*p)

{//在带头结点的双链表中，删除结点*p，设*p为非终端结点

p->prior->next=p->next//①

p->next->prior=p->prior//②

free(p)//③

}

建立一个单链表，实现插入与删除功能的代码如下：

///单链表

#include<iostream>

using namespace std

typedef int elemtype //数据类型模版

struct Lnode //结点

{

elemtype data

Lnode *next

}

///建表

void creat_Link(Lnode &head)

{

Lnode *p,*q

int n

p=new Lnode

head=p

cout<<"输入链表长度:"<<endl

cin>>n

cout<<"输入数据:"<<endl

cin>>p->data

q=p

for(int i=1i<=n-1i++)

{

p=new Lnode

//cout<<"输入数据:"

cin>>p->data

q->next=p

q=p

}

q->next=NULL

}

///表的输出

void output_Link(Lnode *&head)

{

if(head==NULL)

{cout<<"空链表!"<<endl

return}

Lnode *q

q=head

//cout<<"此链表为:"

while(q!=NULL)

{

cout<<q->data<<" "

q=q->next

}

cout<<endl

}

///表的插入

void insert_Link(Lnode *&head)

{

int i

cout<<"输入要插入的位置:"

cin>>i

Lnode *q,*iq

q=head

for(int j=1j<ij++)

{

iq=q

q=q->next

}

cout<<"输入插入的数据:"

Lnode *p

p=new Lnode

cin>>p->data

p->next=iq->next

iq->next=p

cout<<endl

}

///表的数据删除

void Delete_Link(Lnode *&head)

{

cout<<"输入删除的位置:"

int i

cin>>i

if(i==1)

head=head->next

else

{

Lnode *p,*q

q=head

for(int j=1j<ij++)

{p=q

q=q->next

}

p->next=q->next

delete q

cout<<endl

}

}

int main()

{

Lnode *head

head=NULL

creat_Link(head)

insert_Link(head)

output_Link(head)

Delete_Link(head)

output_Link(head)

return 0

}

[扩展]

以“结点的序列”表示线性表称作线性链表（单链表），链表中的数据是以结点来表示的，每个结点的构成：元素(数据元素的映象) + 指针(指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。

---