模拟实现:
public class DoubleLinkedList {static class ListNode{int data;ListNode next;ListNode prev;public ListNode(int val){this.data=val;this.next=null;this.prev=null;}}public ListNode head;//标记头public ListNode last;//标记尾//遍历打印链表public void display(){ListNode cur=this.head;while(cur!=null){System.out.print(cur.data+" ");cur=cur.next;}System.out.println();}//尾插法public void addLast(int val){ListNode node=new ListNode(val);if(this.head==null) {this.head = node;this.last = node;}else{this.last.next=node;node.prev=this.last;this.last=node;}}//头插法public void addFirst(int val){ListNode node=new ListNode(val);if(this.head==null) {this.head = node;this.last = node;}else{node.next=this.head;this.head.prev=node;this.head=node;}}//任意位置插入,第一个数据节点为0号下标public void addIndex(int index,int val){ListNode node=new ListNode(val);ListNode cur=this.head;int count=0;while(cur!=null){cur=cur.next;count++;}if(index<0||index>count){throw new RuntimeException("下标不合理");}if(index==0){addFirst(val);return;}if(index==count){addLast(val);return;}cur=this.head;for(int i=0;i<index;i++){cur=cur.next;}cur.prev.next=node;node.prev=cur.prev;node.next=cur;cur.prev=node;}//查找是否包含关键字key是否在单链表当中public boolean contains(int key){if(this.head==null){return false;}ListNode cur=this.head;while(cur!=null){if(cur.data==key){return true;}}return false;}//删除第一次出现关键字为key的节点public void remove(int key){ListNode newHead=new ListNode(-1);//设置一个虚头节点,就可以不用单独处理删除头节点的情况newHead.next=head;head.prev=newHead;ListNode cur=head;while(cur!=null){if(key==cur.data&&cur.next!=null){//当是中间结点时cur.prev.next=cur.next;cur.next.prev=cur.prev;head=newHead.next;break;}else if(key==cur.data&&cur.next==null){//当是尾结点时cur.prev.next=null;head=newHead.next;break;}cur=cur.next;}}//删除所有值为key的节点 之遍历链表一遍public void removeAll(int key){ListNode newHead=new ListNode(-1);//设置一个虚头节点,就可以不用单独处理删除头节点的情况newHead.next=head;head.prev=newHead;ListNode cur=head;while(cur!=null){if(key==cur.data&&cur.next!=null){//当是中间结点时cur.prev.next=cur.next;cur.next.prev=cur.prev;cur=cur.next;}else if(key==cur.data&&cur.next==null){//当是尾结点时cur.prev.next=null;cur=cur.next;}else{cur=cur.next;}}head=newHead.next;}//链表长度public int size(){ListNode cur=head;int len=0;while(cur!=null){len++;cur=cur.next;}return len;}//链表清空public void clear(){this.head=null;}
}
测试代码:
public class Test {public static void main(String[] args) {DoubleLinkedList linkedList = new DoubleLinkedList();linkedList.addLast(1);linkedList.addLast(1);linkedList.addLast(1);linkedList.addLast(2);linkedList.addLast(3);linkedList.addLast(4);linkedList.addLast(5);linkedList.display();linkedList.addIndex(0,10);linkedList.display();linkedList.addIndex(8,20);linkedList.display();linkedList.addIndex(4,30);linkedList.display();boolean flg=linkedList.contains(10);System.out.println(flg);linkedList.remove(10);linkedList.display();linkedList.remove(20);linkedList.display();linkedList.remove(30);linkedList.display();linkedList.removeAll(1);linkedList.display();int len=linkedList.size();System.out.println(len);linkedList.clear();}
}
运行结果:
