8129319538

java中使用嵌套类来实现链表中节点的抽象数据类型

private class Node { 

Item item; /占位符,

Node next; /指向下一个节点 

}

因此我们能用该链表处理任意类型数据类型  构造链表数据,初始化链表节点,默认调用了无参构造函数item和next初始值都为null

Node one=new Node(); 

Node two=new Node(); 

Node three=new Node(); 

one.item="1"; 

two.item="2";

three.item="3";

one.next=two; /one节点的next指向two 

two.next=three;/two节点的next指向three

从表头插入节点

Node oldOne=one; /保存表头节点 

Node newOne=new Node(); /创造新节点 

newOne.item="new1"; /新节点赋值 

newOne.next=oldOne; /新节点newOne的next指向久的头节点

从表头删除节点,之前的one节点就变成孤儿节点,java内存回收机制会把它回收

 one=one.next;

在表位插入节点

Node newNode=new Node(); 

three.next=newNode; 

newNode.item="newNode";

在其他位置的插入和删除操作
比如删除链表尾部节点,我们只能遍历链表找到last节点的前一个节点,也就是next指向last的节点,它花费的时间和链表长度成正比,所以实现任意插入和删除操作的标准方案是双向链表,意味着Node类中有Node pre局部变量之前当前节点的前一个节点
遍历节点

 for(Node x=first;x!=null;x=x.next)
 {
 /处理x.item
 }

用链表实现栈,注意当链表元素为空时,pop操作

public class Stack<Item> implements Iterable<Item> {

private Node first; / the top element of stack

private int N; / the number of elements

privateclass Node {

Item item;

Node next;

}

public boolean isEmpty() {

return first == null;

}

public int size() {

return N;

}

/ push element in stack top

public void push(Item item) {

Node oldFirst = first;

first = new Node();

first.item = item;

first.next = oldFirst;

N++;

}

/ pop element in stack top

public Item pop() {

if (isEmpty()) {

first = null;

return null;

}

Item item = first.item;

first = first.next;

N--;

return item;

}

@Override

public Iterator<Item> iterator() {

/ TODO Auto-generated method stub

return new ListIterator();

}

private class ListIterator implements Iterator<Item> {

private Node current = first;

public boolean hasNext() {

return current != null;

}

public void remove() {

}

public Item next() {

/ TODO Auto-generated method stub

Item item = current.item;

current = current.next;

return item;

}

}

public static void main(String[] args) {

/ TODO Auto-generated method stub

Stack<String> s = new Stack<String>();

s.push("one");

s.push("twon");

s.push("tree");

s.pop();

s.pop();

s.pop();

s.pop();

Iterator iterator = s.iterator();

while (iterator.hasNext()) {

String t = (String) iterator.next();

System.out.println(t);

}

}

}