前言

大家好，我是Maybe。最近在學習數據結構中的鏈表，自己手動實現了一個LinkedList。我想與大家分享一下。

思維導圖

代碼部分

package Constant;public class constant {public static final String INDEX_IS_WRONG="輸入的下標不合法";
}

package utils;public class IndexException extends RuntimeException{public IndexException() {super();}public IndexException(String message) {super(message);}
}

public interface IList {// 頭插法public void addFirst(int data);// 尾插法public void addLast(int data);// 任意位置插入，第一個數據節點為0號下標public void addIndex(int index,int data);// 查找是否包含關鍵字key是否在單鏈表當中public boolean contains(int key);// 刪除第一次出現關鍵字為key的節點public void remove(int key);// 刪除所有值為key的節點public void removeAllKey(int key);// 得到鏈表的長度public int size();public void display();public void clear();
}

import Constant.constant;
import utils.IndexException;public class LinkedList implements IList {//1.定義一個內部類static class ListNode{public int val;//類型寫成了String,應該是ListNode的public ListNode prev;public ListNode next;public ListNode(int val) {this.val = val;}}public ListNode head;//這個就要給個尾了public ListNode last;@Overridepublic void addFirst(int data) {if(head==null){ListNode node=new ListNode(data);head=last=node;}else{ListNode node=new ListNode(data);node.next=head;head.prev=node;head=node;}}@Overridepublic void addLast(int data) {if(head==null){ListNode node=new ListNode(data);//寫成了node=last=null了head=last=node;}else{ListNode node=new ListNode(data);last.next=node;node.prev=last;//這里要注意last=last.next;}}@Override//在LinkedList中找到對應的cur，然后再cur之前插入public void addIndex(int index, int data) {int len=size();if(index<0||index>len){String msg= constant.INDEX_IS_WRONG+index;throw new IndexException(msg);}if(index==0){addFirst(data);}else if(index==len){addLast(data);}else{ListNode node=new ListNode(data);ListNode cur=findIndex(index);node.next=cur;cur.prev.next=node;node.prev=cur.prev;cur.prev=node;}}//在LinkedList中找到對應的curprivate ListNode findIndex(int index){if(head==null){return null;}else{ListNode cur=head;while(index!=0){cur=cur.next;index--;}return cur;}}@Overridepublic boolean contains(int key) {if(head==null){return false;}else{ListNode cur=head;while(cur!=null){if(cur.val==key){return true;}else{cur=cur.next;}}return false;}}@Overridepublic void remove(int key) {//1.先判斷鏈表是否為空if(head==null){return;}else{ListNode cur=head;while(cur!=null){if(cur.val==key){//1.考慮頭刪的情況if(cur==head){head=head.next;//考慮如果鏈表中只有一個節點的情況if(head!=null){head.prev=null;}}else{cur.prev.next=cur.next;//尾巴節點和中間節點共用if(cur.next==null){//尾節點last=last.prev;}else{//中間節點cur.next.prev=cur.prev;}}return;}cur=cur.next;}}}@Overridepublic void removeAllKey(int key) {if(head==null){return;}else{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){last=last.next;}else{cur.next.prev=cur.prev;}}}cur=cur.next;}}}@Overridepublic int size() {if(head==null){return 0;}else{ListNode cur=head;int count=0;while(cur!=null){cur=cur.next;count++;}return count;}}@Overridepublic void display() {if(head==null){return;}else{ListNode cur=head;while(cur!=null){System.out.print(cur.val+" ");cur=cur.next;}System.out.println();}}@Overridepublic void clear() {if(head==null){return;}else{ListNode cur=head;while(cur!=null){ListNode curN=cur.next;cur.prev=null;cur.next=null;cur=curN;}head=last=null;//最后要把head和last置為null}}
}

import utils.IndexException;public class Test {public static void main(String[] args) {LinkedList linkedList=new LinkedList();linkedList.addLast(1);linkedList.addLast(1);linkedList.addLast(1);linkedList.addLast(2);linkedList.display();
//        linkedList.addFirst(1);
//        linkedList.addFirst(2);
//        linkedList.addFirst(3);
//        linkedList.addFirst(4);
//        linkedList.display();
//        int ret=linkedList.size();
//        System.out.println(ret);
//        try{
//            linkedList.addIndex(2,100);
//
//        }catch (IndexException e){
//            e.printStackTrace();
//        }
//        linkedList.display();
//        linkedList.remove(1);
//        linkedList.display();
//        linkedList.removeAllKey(1);linkedList.clear();linkedList.display();}
}

結語?

本次分享到此結束啦。希望可以幫到有需要的人！

?

?

?

?

?

?