一、實現MyDLinkedList（雙向鏈表）

package LinkedList;public class MyDLinkedList {//首先我們要創建節點（因為雙向鏈表和單向鏈表的節點不一樣！！）static class Node{public String val;public Node prev = null;public Node next = null;//給一個構造方法public Node(String val) {this.val = val;}}//表示整個鏈表，此處不引入傀儡節點，使用Null表示空的鏈表public Node head = null;//為了方便后續的尾插曹祖public Node tail = null;//給一個toStirng的打印@Overridepublic String toString() {StringBuilder stringBuilder = new StringBuilder();stringBuilder.append("[");//進行鏈表的遍歷for(Node cur = head;cur!= null ;cur = cur.next){stringBuilder.append(cur.val);if(cur.next != null) {stringBuilder.append(",");}}stringBuilder.append("]");return stringBuilder.toString();}//接下來來實現一些雙向鏈表的核心操作//1.實現頭插操作public void addFirst(String val){Node newNode = new Node(val);//首先判斷鏈表是否為空的情況if(head == null){head = newNode;tail = newNode;}else {//再來看看一般情況newNode.next = head;head. prev = newNode;//2.讓head指向新節點head = newNode;}}//2.實現鏈表的尾插操作public void addLast(String val){Node newNode = new Node(val);//1.首先判斷鏈表為空的情況，可知與頭插操作一樣if(head == null){head = newNode;tail = newNode;}else {//2.考慮一般情況tail.next = newNode;newNode.prev = tail;tail = newNode;}}//實現鏈表長度的計算public int size(){int size =0;for(Node cur = head;cur != null;cur = cur.next){size++;}return size;}//3.實現雙向鏈表的按位置插入public void add(int index,String val){int size = size();//1.首先判斷index的值是否合法if( index < 0 || index > size ){throw  new IndexOutOfBoundsException("Index:"+index+",Size:"+size);}//2.判斷特殊位置if(index ==0 ){//此時就是頭插操作addFirst(val);return;}if(index== size){//此時就是尾插addLast(val);return;}//3.進行一般的插入//先找到要插入節點的前一個節點Node prev = head;for(int i =0;i<index-1;i++){prev = prev.next;}//此時我們已經找到了要插入節點的前一個節點Node newNode = new Node(val);Node next = prev.next;//首先建立新節點與上一個節點之間的關系prev.next = newNode;newNode.prev = prev;//再建立新節點與下一個節點之間的關系newNode.next = next;next.prev = newNode;}//4.實現包含查找操作public Boolean contains(String val){for (Node cur = head ; cur != null;cur = cur.next){if(cur.val.equals(val)) {return true;}}return false;}//5.查找元素，返回該元素的下標，如果沒有找到，返回-1public int indexOf(String val){int index =0;for (Node cur = head;cur != null;cur =cur.next){if(cur.val.equals(val)){return  index;}index++;}return -1;}//6.頭刪public void removeFirst(){//1.首先考慮是否為空鏈表if(head == null){return;//空鏈表無法進行刪除操作}//2.考慮只有一個節點的情況if(head.next == null){head = null;tail = null;return;}//3.考慮一般情況head = head.next;head.prev = null;}//7.尾部刪除public void removeLast(){//1.考慮空鏈表if (head == null){return;}//2.考慮只有一個節點if(head.next == null){head = null;tail = null;return;}//3.考慮一般情況tail = tail.prev;tail.next = null;}//8.指定位置刪除public void remove(int index){int size = size();//對index做判斷if(index <0 || index >= size){throw  new IndexOutOfBoundsException("index:"+index+",size:"+size);}//2.如果是刪除index=0if(index ==0){removeFirst();return;}if(index ==size-1){removeLast();return;}//3.考慮一般情況的刪除//先找到前一個節點Node prev = head;for(int i =0;i<index-1;index++){prev = prev.next;}Node toRemove = prev.next;Node next = toRemove.next;//4.進行刪除操作prev.next = next;next.prev =prev;}//9.指定值刪除public void remove(String val){//1.首先考慮空的鏈表if(head == null){return ;}//2.判定頭刪/尾刪操作if(val.equals(head.val)){removeFirst();return;}if(val.equals(tail.val)){removeLast();return;}//3.一般情況 先找到前一個節點Node toRemove = head;for (;toRemove!=null;toRemove= toRemove.next){if(toRemove.val.equals(val)){break;}}//循環之外有兩種情況一種是找到了打破循環 另一種是循環走完了！if(toRemove == null){return ;}Node prev = toRemove.prev;Node next = toRemove.next;prev.next = next;next.prev = prev;}//10.鏈表的清空操作public void clear(){head = null;tail = null;}public static void test(){MyDLinkedList list = new MyDLinkedList();list.addFirst("a");list.addFirst("b");list.addFirst("c");System.out.println(list);}public static  void test1(){MyDLinkedList list = new MyDLinkedList();list.addLast("c");list.addLast("b");list.addLast("a");System.out.println(list);}public static void test3(){MyDLinkedList list = new MyDLinkedList();list.addFirst("a");list.addFirst("a");list.addFirst("a");list.addFirst("a");list.add(0,"b");list.add(2,"c");System.out.println(list);}public static void test4(){MyDLinkedList list = new MyDLinkedList();list.addFirst("a");list.addFirst("a");list.addFirst("a");list.addFirst("a");list.add(0,"b");list.add(2,"c");System.out.println(list);System.out.println(list.indexOf("a"));System.out.println(list.contains("b"));System.out.println(list.contains("d"));}public static void test5() {MyDLinkedList list = new MyDLinkedList();list.addFirst("a");list.addFirst("a");list.addFirst("a");list.addFirst("a");list.add(0, "b");list.add(2, "c");System.out.println(list);list.removeFirst();list.removeFirst();System.out.println(list);}public static void test6() {MyDLinkedList list = new MyDLinkedList();list.addFirst("a");list.addFirst("a");list.addFirst("a");list.addFirst("a");list.add(0, "b");list.add(2, "c");System.out.println(list);list.removeLast();list.removeLast();System.out.println(list);}public static void test7() {MyDLinkedList list = new MyDLinkedList();list.addFirst("a");list.addFirst("a");list.addFirst("a");list.addFirst("a");list.add(0, "b");list.add(2, "c");System.out.println(list);list.remove(1);list.remove(4);System.out.println(list);}public static void test8() {MyDLinkedList list = new MyDLinkedList();list.addLast("a");list.addLast("b");list.addLast("c");System.out.println(list);list.remove("a");System.out.println(list);}public static void main(String[] args) {//  test();// test1();//test3();// test4();//test5();//test6();//test7();//test8();}
}