java数据结构之链表(2)
白天贴了一个链表的数据结构，基本上都是看着书写的，晚上自己动手写了一个，这里贴出来给大家砸鸡蛋哈，http://www.agoit.com/images/smiles/icon_biggrin.gif1，链表节点
package pku.ss.datastructure.ILinkedList;public interface ILinkedList {/** * get the size of the list * @return the size of the list */public int getSize();/** * Judge that if the list is empty * @return true or false */public boolean isEmpty();/** * make the list empty */public void makeEmpty();/** * Judge that if the list contains the node whose element equals x * @param x * @return true or false */public boolean contains(Object x);/** * remove the node whose element equals x, and return a* boolean value that if there is a x in list then return true, * else return false * @param x * @return true or false */public boolean remove(Object x);/** * Insert a node behind k'st into list with node's element equals x * @param x * @param k * @return true or false */public boolean insert(Object x, int k);/** * get the first element of list * @return element of the first node */public Object getFirst();/** * get the last element of list * @return element of the last node */public Object getLast();/** * print the elements of the list */public void printList();}
2,链表结构
package pku.ss.datastructure.LinkedList;import pku.ss.datastructure.ILinkedList.ILinkedList;public class LinkedList implements ILinkedList {private int size;private ListNode header;/** * Initialize a list with max capability of 0 ** @param size */public LinkedList() {this.size = 0;header = new ListNode(null);}@Overridepublic boolean contains(Object x) {if (size == 0) {System.out.println("The list is empty!");return false;}ListNode temp = header.next;while (temp != null && !temp.element.equals(x))temp = temp.next;if (temp == null)return false;elsereturn true;}@Overridepublic Object getFirst() {if (size == 0) {System.out.println("The list is empty");return null;}return header.next.element;}@Overridepublic Object getLast() {if (size == 0) {System.out.println("The list is empty");return null;}ListNode temp = header.next;while (temp.next != null)temp = temp.next;return temp.element;}@Overridepublic int getSize() {return this.size;}public boolean insert(Object x) {return insert(x, 0);}@Overridepublic boolean insert(Object x, int k) {if (size < k)return false;int count = 0;ListNode temp = header;while (count < k && temp.next != null) {temp = temp.next;count++;}ListNode aNode = new ListNode(x);aNode.next = temp.next;temp.next = aNode;size++;return true;}@Overridepublic boolean isEmpty() {if (size != 0)return false;elsereturn true;}@Overridepublic void makeEmpty() {header = null;size = 0;}@Overridepublic boolean remove(Object x) {if (!contains(x))return false;ListNode temp = header;while (temp.next != null && !temp.next.element.equals(x))temp = temp.next;temp.next = temp.next.next;size--;return true;}public void printList() {if (size == 0)System.out.println("The list is Empty");else {ListNode temp = header.next;while (temp != null) {System.out.print(temp.element + " ");temp = temp.next;}}System.out.println();System.out.println("***************************");}}
3，测试类
package pku.ss.datastructure.Demo;import pku.ss.datastructure.LinkedList.LinkedList;public class LinkedListDemo {public static void main(String[] args) {LinkedList list = new LinkedList();list.insert("H");list.insert("G");list.insert("F");list.insert("E");list.insert("D");list.insert("C");list.insert("B");list.insert("A");list.printList();list.remove("A");list.printList();list.insert("D1", 3);list.printList();if (list.isEmpty())System.out.println("Empty");elselist.printList();System.out.println("The list's size is: " + list.getSize());System.out.println("*******************");System.out.println("The first element is: " + list.getFirst());System.out.println("*******************");System.out.println("The last element is: " + list.getLast());System.out.println("*******************");list.makeEmpty();if (list.isEmpty())System.out.println("Empty");elselist.printList();}}
页:
[1]