LinkedList主要类：
class LinkedNode{ public int data = 0; public LinkedNode next = null; public LinkedNode(int data) { this.data = data; } } public class LinkedList { //创建头结点 private LinkedNode head = null; //头插 public void addFrist(int elem) { LinkedNode node = new LinkedNode(elem); if(this.head == null) {//空链表 this.head = node; return; } node.next = head; this.head = node; return; } //尾插 public void addLast(int elem) { LinkedNode node = new LinkedNode(elem); if(head == null) {//空链表 this.head = node; return; } LinkedNode cur = this.head; //循环结束，cur一定为最后一个节点 while(cur.next != null) { cur = cur.next; } cur.next = node; return; } //任意位置插入 public void addIndex(int index,int elem) { LinkedNode node = new LinkedNode(elem); int len = size(); if(index < 0 || index > len) { return; } if(index == 0) { addFrist(elem); return; } if(index == len) { addLast(elem); return; } LinkedNode prev = getIndexPos(index - 1); node.next = prev.next; prev.next = node; } //判断元素是否存在 public boolean contains(int toFind) { for(LinkedNode cur = this.head; cur != null;cur = cur.next) { if(cur.data == toFind) { return true; } } return false; } //删除第一次出现的关键字为Key的元素 public void remove(int toRemove) { if(head == null) { return; } if(head.data == toRemove) { this.head = this.head.next; return; } LinkedNode prev = searchPrev(toRemove); if(prev == null) { return; } //prev.next = prev.next.next; LinkedNode nodeToRemove = prev.next; prev.next = nodeToRemove.next; } //删除所有关键字为Key的元素 public void removeAll(int toRemove) { if(head == null) { return; } LinkedNode prev = head; LinkedNode cur = head.next; while(cur != null) { if(cur.data == toRemove) { //删除cur对应节点 prev.next = cur.next; cur = prev.next; } else { //cur对应节点不删除 prev = cur; cur = cur.next; } } //头结点的情况 if(this.head.data == toRemove) { this.head = this.head.next; } return; } private LinkedNode searchPrev(int toRemove) { //找到要删除元素的前一个位置 if(this.head == null) { return null; } LinkedNode prev = this.head; while(prev.next != null) { if(prev.next.data == toRemove) { return prev; } prev = prev.next; } return null; } //获取index-1 public LinkedNode getIndexPos(int index) { LinkedNode cur = this.head; for(int i=0;i<index;i++) { cur = cur.next; } return cur; } //求长度 public int size() { int size =0; for(LinkedNode cur = head; cur!=null;cur = cur.next) { size++; } return size; } //打印 public void dispaly() { System.out.print("["); for(LinkedNode node = this.head; node != null; node = node.next) { System.out.print(node.data); if(node.next != null) { System.out.print(","); } } System.out.println("]"); } public void clear() { //java垃圾回收机制 this.head = null; } }Test测试代码：
public class Test { public static void main(String[] args) { TestAddFrist(); TestAddLast(); TestAddIndex(); TestContains(); TestRemove(); TestRemoveAll(); TestClear(); } public static void TestAddFrist() { LinkedList list = new LinkedList(); System.out.println("头插法："); list.addFrist(1); list.addFrist(2); list.addFrist(3); list.addFrist(4); list.dispaly(); } public static void TestAddLast() { LinkedList list = new LinkedList(); System.out.println("尾插法："); list.addLast(1); list.addLast(2); list.addLast(3); list.addLast(4); list.dispaly(); } public static void TestAddIndex() { LinkedList list = new LinkedList(); System.out.println("任意位置插入："); list.addLast(1); list.addLast(2); list.addLast(3); list.addLast(4); list.addIndex(2, 6); list.dispaly(); } public static void TestContains() { LinkedList list = new LinkedList(); System.out.println("判断元素是否存在："); list.addLast(1); list.addLast(2); list.addLast(3); list.addLast(4); boolean ret = list.contains(6); System.out.println("ret="+ret); } public static void TestRemove() { LinkedList list = new LinkedList(); System.out.println("删除第一次出现的关键字为Key的元素:"); list.addLast(1); list.addLast(2); list.addLast(3); list.addLast(4); list.addLast(3); list.addLast(3); list.addLast(2); list.remove(4); list.dispaly(); } public static void TestRemoveAll() { LinkedList list = new LinkedList(); System.out.println("删除所有关键字为Key的元素："); list.addLast(1); list.addLast(2); list.addLast(3); list.addLast(4); list.addLast(3); list.addLast(3); list.addLast(2); list.removeAll(3); list.dispaly(); } public static void TestClear() { LinkedList list = new LinkedList(); System.out.println("清空链表："); list.addLast(1); list.addLast(2); list.addLast(3); list.addLast(4); list.clear(); list.dispaly(); } }运行结果：
