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

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

}

}

1、链表建立需要节点。这是存储数据的基础，以C++语言为例，要建立这样的节点(假设存储信息的类型作为一个模板)

template <class DataType>

struct Node{

DataType info //节点存储的信息

Node<DataType>*next

}

2、因为你是使用指针，那么，就需要动态创建结构体。使用new 运算符在堆内存中创建

Node<DataType>*head = new Node<DataType>

堆内存和栈不同，你动态申请和释放都是在堆内存里，所以你不用担心调用一个函数，在

这个函数里动态申请了内存，返回之后没有了，在的。

3、插入节点

我们以插入头结点后边为例：

假设函数原型为：

void AddToFirst( Node<DataType>* head, DataType data )

那么函数主体中这样写：

{

Node<DataType>* ptr = new Node<DataType> //动态生成一个新的节点

ptr->info = data //存储传递过来的DataType类型的数据

ptr->next = head->next //先让ptr指向的地方为head指向的地方

head->next = ptr //再让头结点指向ptr

}

这样，添加到头结点之后的动作就完成了。

4、删除 *** 作

删除 *** 作需要查找是否存在要删除的数据，存在则删除，不存在不采取动作

函数原型：

void DeleteNode ( Node<DataType>*head, DataType data )

我们设置ptr作为遍历链表的游标，设置ptrNext指针作为ptr的下一个节点，将它里面的info与data对比；

设置两个指针是为了方便我们删除节点。

函数定义如下

{

Node<DataType>*ptr = head

Node<DataType>*ptrNext = prt->next

while( ptrNext &&ptrNext->info != data ){ //当ptrNext不是NULL且包含的数据不等于data时

ptr = ptrNext

ptrNext = ptrNext->next //ptr和ptrNext均往下移动一次

}

if( ! ptrNext ) //如果ptrNext == NULL

cout <<"链表中不存在此数据：" <<data <<endl

else{//那么跳出循环的情况就只能是ptrNext->info == data啦，此处删除ptrNext

ptr->next = ptrNext->next //释放ptrNext指向的堆内存之前，要把

//ptrNext之前的节点，也就是ptr，将其指向prtNext指向的地方

delete ptrNext //释放堆内存

cout <<"删除成功！" <<endl

}

}

关于链表的建立、添加节点、删除节点，还需要你自己多多琢磨。

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

///单链表

#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

}

[扩展]

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

---