【Java数据结构】双向 不带头 非循环 链表实现（模拟实现LinkedList类）

LinkedList底层实际上是双向、不带头结点、非循环的链表

链表的分类有八种，常用的有两种：一是单向、不带头结点、非循环的（基本上网上的题型都是这种）；二是双向、不带头结点、非循环（LinkedList的底层实现）

/*** 模拟实现LinkedList*/class MyLinkedList{static class ListNode{public int val;public ListNode prev;public ListNode next;public ListNode(int val){this.val=val;}}public ListNode head;//永远指向头节点public ListNode last;//永远指向尾节点//得到链表的长度public int size(){ListNode cur=head;int count=0;while(cur!=null){count++;cur=cur.next;}return count;}//显示链表public void display(){ListNode cur=head;while(cur!=null){System.out.print(cur.val+" ");cur=cur.next;}}//清空链表public void clear(){//下述代码可有可无/* ListNode cur=head;while(cur!=null){ListNode curNext=cur.next;cur.prev=null;cur.next=null;cur=cur.next;}*/this.head=null;this.last=null;}//查找是否包含关键字key是否在单链表当中public boolean contains(int key){ListNode cur=head;while(cur!=null){if(cur.val==key){return true;}cur=cur.next;}return false;}//头插法public void addFirst(int data){ListNode node=new ListNode(data);if(head==null){head=node;last=node;return ;//记得return. 不然下面加else，因为这是两种不同的情况}node.next=head;head.prev=node;head=node;}//尾插法public void addLast(int data){ListNode node =new ListNode(data);if(last==null){last=node;head=node;return;}last.next=node;node.prev=last;last=node;//last=last.next}//删除第一次出现关键字为key的节点public void remove(int key){ListNode cur=head;while(cur!=null) {if (cur.val == key) {//开始删if (cur == head) {//删除头结点head = head.next;if (head != null) {head.prev = null;}} else {cur.prev.next = cur.next;if (cur.next != null) {cur.next.prev = cur.prev;} else {last = last.prev;}}}cur=cur.next;}}//删除所有值为key的节点public void removeAllKey(int key){if(head==null){return;}ListNode cur=head.next;ListNode prev=head;while(cur!=null){if(cur.val==key){prev.next=cur.next;}else{prev=cur;}cur=cur.next;}if(head.val==key){head=head.next;}}//任意位置插入,第一个数据节点为0号下标public void addIndex(int index,int data){if(index<0||index>size()){System.out.println("输入下标不合法");}if(index==0){addFirst(data);}   if(index==size()){addLast(data);}  ListNode cur=head;while(index!=0){cur=cur.next;index--;}ListNode node=new ListNode(data);node.next=cur;cur.prev.next=node;node.prev=cur.prev;cur.prev=node;}
}