手写链表的Java实现

package test;class Node{//数据域private Object ele;//指针域private Node node;//默认构造器，标准构造器public Node() {this(null,null);}public Node(Object ele,Node node) {this.ele=ele;this.node=node;}//设置操作数据域的接口方法public Object getEle() {return ele;}public void setEle(Object ele) {this.ele = ele;}//设置操作指针域的接口方法public Node getNext() {return node;}public void setNext(Node node) {this.node = node;}}class AB{//比较两个元素是否相等（引用比较）public static boolean compare(Node a,Node b) {if (a.getEle()==b.getEle() && a.getNext()==b.getNext())return true;return false;}//比较两个元素是否相等（内容比较）//必须重写 节点 数据对象的 equalspublic static boolean compareContent(Node a,Node b) {if (a.getEle().equals(b.getEle()))return true;return false;}}/*** 说明：* 本链表的构造函数默认为有头空链表，* 需要添加元素请使用 add /insert / preAdd；* 由于节点之间比较的复杂性，本链表节点之间的比较特别定义使用了 AB * 这个类的 compare方法，应对更多的情况。* @author Tomsan**/public class ListSLinked{//链表的首节点（有头节点）private Node head;//链表的大小private int size;//使用默认构造方法；创建有头空链表public ListSLinked() {this.head = new Node();}//判空public boolean isEmpty() {return this.size==0;}//返回链表的大小public int getSize() {return size;}//获取某个元素e节点的前驱节点(引用有效)public Node getPre(Node e) {Node temp = this.head;// head 不是元素，而是空表头while (temp.getNext() != null) {Node pre = temp;temp = temp.getNext();if (temp == e) return pre;}return null;}// 获取 i 号 节点的元素的前驱节点public Node getPre(int i) {if (i>this.size-1) return null;Node temp = this.head;for (int j=0; j<=i;j++) {temp = temp.getNext();}return temp;}//获取 i 号元素所在的节点public Node getEleById(int i) {Node pre = getPre(i);return pre.getNext();}//内容判断链表是否含有元素 epublic boolean contain(Node e) {Node temp = this.head;while (temp.getNext()!=null) {temp = temp.getNext();if (pareContent(temp, e)) { // 用到AB类的比较策略return true;}}return false;}//判断 e 在链表中的 idpublic int getIdByEle(Node e) {Node temp = this.head;int id = -1;while (temp.getNext()!=null) {id++;temp = temp.getNext();if (pareContent(temp,e))return id;}return -1;}//在 i 号位置插入 元素public boolean insertEle(int i,Node e) {Node temp = this.head;if (0<=i && i<=size) {//先找到 第 i-1 号 元素 for (int j=0;j<i;j++) {temp = temp.getNext();}Node tempLast = temp.getNext();temp.setNext(e);e.setNext(tempLast);this.size++;return true;}return false;}//删除 i 号 元素public boolean delete(int i) {Node temp = this.head;if (0<i && i<=size) {//先找到 第 i-1 号 元素 for (int j=0;j<i;j++) {temp = temp.getNext();}temp.setNext(temp.getNext().getNext());return true;}return false;}//尾部添加元素public void append(Node node) {Node temp = head;//链表不为空while(temp.getNext()!=null) {temp = temp.getNext(); }temp.setNext(node);//如果只含链表头if (head.getNext()== null) {temp.setNext(node);}this.size++;}//打印链表内容public void printLindedList() {Node temp = this.head;while (temp.getNext()!=null) {temp = temp.getNext();System.out.print(temp.getEle()+" ");}}}

测试Java链表

package test;public class Test {public static void main(String[] args) throws InterruptedException {ListSLinked ls = new ListSLinked();//构造20个元素的链表for(int i=0; i<20;i++) {ls.append(new Node("ok"+i,null));}// 显示列表结果System.out.println("构造20个元素的链表");ls.printLindedList();//在序号 2 处插入元素 Node("第三")ls.insertEle(2, new Node("第三 ",null));// 显示列表结果System.out.println("\n插入第三");ls.printLindedList();//删除 第 i 号元素ls.delete(2);// 显示列表结果System.out.println("\n删除第三");ls.printLindedList();//是否包含某元素boolean flag = ls.contain(new Node("ok2",null));// 显示列表结果System.out.println("是否包含"+ flag);}}