java数据结构之链表
近日复习数据结构，以前都是用c写的程序，现在用java来将其重新实现，希望大家批评指正：1，节点说明：
package pku.ss.datastructure.LinkedList;public class ListNode {ListNode(Object theElement) {this(theElement, null);}ListNode(Object theElement, ListNode n) {element = theElement;next = n;}Object element;//节点中的元素ListNode next; //指向下一个节点}
2，枚举器类
package pku.ss.datastructure.LinkedList;/** * 是一个枚举器（iterator）类，它提供了用于读取元素的方法 LinkedListItr存储 * 对ListNode对象的一个引用，它代表枚举器 的位置 ** @author Jacken */public class LinkedListItr {LinkedListItr(ListNode theNode) {current = theNode;}/** * 判断当前节点是否是最后一个节点 * @return true or false */public boolean isPastEnd() {return current == null;}/** * 返回当前节点的元素值 * @return 当前节点的元素值 */public Object retrieve() {return isPastEnd() ? null : current.element;}/** * 将当前节点往后推后一个节点 */public void advance() {if (!isPastEnd())current = current.next;}ListNode current;}
3，链表类
package pku.ss.datastructure.LinkedList;public class LinkedList {public LinkedList() {header = new ListNode(null);}/** * 判断链表是否为空 * @return true or false */public boolean isEmpty() {return header.next == null;}/** * 将链表置空 */public void makeEmpty() {header.next = null;}/** * 返回头节点的枚举器 * @return 头节点枚举器 */public LinkedListItr zeroth() {return new LinkedListItr(header);}/** * 返回第一个节点的枚举器 * @return 第一个节点的枚举器 */public LinkedListItr first() {return new LinkedListItr(header.next);}/** * 查找指定元素 * @param x * @return 所查找元素的枚举器 */public LinkedListItr find(Object x) {ListNode itr = header.next;while (itr.next != null && !itr.element.equals(x))itr = itr.next;return new LinkedListItr(itr);}/** * 删除指定元素 * @param x */public void remove(Object x) {LinkedListItr p = findPrevious(x);if (p.current.next != null)p.current.next = p.current.next.next;}/** * 查找指定元素的头一个节点 * @param x * @return 指定元素的头一个节点的枚举器 */public LinkedListItr findPrevious(Object x) {ListNode itr = header;while (itr.next != null && !itr.next.element.equals(x))itr = itr.next;return new LinkedListItr(itr);}/** * 在P几点后面插入一个节点，节点的元素值为x * @param x * @param p */public void insert(Object x, LinkedListItr p) {if (p != null && p.current != null)p.current.next = new ListNode(x, p.current.next);}/** * 打印指定链表 * @param theList */public static void printList(LinkedList theList) {if (theList.isEmpty()) {System.out.println("Empty List");} else {LinkedListItr itr = theList.first();for (; !itr.isPastEnd(); itr.advance())System.out.println(itr.retrieve() + " ");}}private ListNode header;}
页:
[1]