[工学]Java数据结构--链表.ppt

* * * * * 双链表的设计(续) public void remove (Node p)throws Exception{ DLinkedNode node = check(p); node.getPre().setNext(node.getNext()); node.getNext().setPre(node.getPre()); size--; } 请设计方法移除尾部元素 public void removeLast() 双链表的设计(续) 请设计方法移除指定位置的元素 public void remove(int index) 请设计方法将链表中指定位置元素替换为指定的元素，并返回以前在指定位置处的元素 public void set(int index,Object obj) 链表的使用 可以使用链表替代数组实现栈和队列。 public class StackLinkedList { private SinglyLinkedNode top;// 指向栈顶元素 private int size;// 栈中元素数目 public StackLinkedList() { top = null; size = 0; } public int getSize() { return size; } public boolean isEmpty() { return (top == null) ? true : false; } 链表的使用 public Object peek() { if (isEmpty()) return null; return top.getData(); } public Object pop() { if (isEmpty()) return null; Object o = top.getData(); top = top.getNext(); size--; return o; } 链表的使用 public void push(Object o) { SinglyLinkedNode n = new SinglyLinkedNode(o, top); top = n; size++; } } 练习 使用DLinkedList实现栈和队列。 使用java.util.LinkedList实现栈和队列。 * * * * * * * * * * * * * * * * * * * * * * * * * * Java数据结构—链表 学习目标 链表的概念 单链表 双链表 数组的缺点 数组是很有用的数据结构，但是有两个局限： 若改变数据的大小就需要创建一个新数组并从原数组中拷贝所有数据至新数组； 数组数据在内存中依次连续存储，向数组中插入一项要移动数组中其他数据。 链表的概念 链表这种数据结构是使用指针(即引用)将存储数据元素的那些单元依次串联在一起。这种方法避免了在数组中用连续的单元存储元素的缺点，因而在插入或者删除时不再需要移动元素来腾出空间或填补空缺。 需要作出的改变就是在每个单元中设置指针来表示表中元素之间的逻辑关系(前还是后)。因此每个单元至少有两个域，一个用于数据元素的存储，一个用于指向其他单元的指针。这种具有一个数据域和多个指针域的存储单元称为节点(Node)。 链表的图示 数据 指针 node(节点) 节点本身就是对象 节点的设计 节点接口 public interface Node { //获取节点数据域 public Object getData(); //设置节点数据域 public void setData(Object obj); } 单链表 a0 next 单链表的每个节点只有一个指向表中下一个节点的指针。第一个节点称为首节点，最后一个称为尾节点。尾节点的特征是next引用为空(null)。 node node a1 next 单链表节点的设计 除了需要实现Node接口定义的获取和设置数据域的两个方法以外，还需要提供对指向下一节点的指针的操作方法。为此提供两个方法，getNext()和setNext(Node node)。 public class SinglyLinkedNode implements Node { private Object obj; private SinglyLinkedNode next; 单链表节点的设计(续) public SinglyLinkedNode() { this(null, null); } public SinglyLinkedNode(Object obj, SinglyLinkedNode next) { this.obj = obj; this.next = ne