手寫一個單向連結清單

主要包括單向連結清單的插入與删除操作

package leetcode.list;

/**
 * @基本功能:手寫一個單連結清單
 * @program:summary
 * @author:peicc
 * @create:2019-08-17 11:45:53
 **/
public class LinkList {
    ListNode head;//頭結點
    ListNode last;//尾結點
    private int size;
    /*連結清單節點*/
    class ListNode{
        int val;//值域
        ListNode  next;//指針域
        //構造函數
        ListNode(int val){
            this.val=val;
            this.next=null;
        }
    }
    /**************主要API**************/
    /***
     * @函數功能：傳回連結清單元素的大小
     * @param :
     * @return：int
     */
    public int getSize() {
        return size;
    }

    /***
     * @函數功能：向連結清單中添加元素
     * @param val:
     * @return：void
     */
    public void add(int val){
        if(head==null){//連結清單為空
            head=new ListNode(val);//添加的結點為目前連結清單的頭結點
            last=head;
        }else{
            last.next=new ListNode(val);//否則，将連結清單添加到末尾結點
            last=last.next;//current指向新添加的結點
        }
        size++;
    }
    /***
     * @函數功能：指定位置前插入元素
     * @param val:待插入的元素
     * @param index:插入位置
     * @return：void
     */
    public void insert(int val,int index){
        if (size==0&&index==0){//原始連結清單為空
            //構造一個新節點
            ListNode newNode=new ListNode(val);
            head=newNode;
            last=newNode;
            size++;
            return;
        }else if (index<0||index>=size) {
            throw new ArrayIndexOutOfBoundsException("待插入元素的位置不合法");
        }
        ListNode cur=head;
        ListNode pre=null;//儲存上一個被通路的結點
        // 找到待插入元素的位置
        for (int i = 0; i <index ; i++) {
            pre=cur;
            cur=cur.next;
        }
        //根據待插入元素構造一個新的結點
        ListNode newNode=new ListNode(val);
        newNode.next=cur;
        if (pre==null) {//在頭結點前插入
            head=newNode;
        }else{
            pre.next=newNode;
        }
        size++;
    }
    /***
     * @函數功能：删除指定位置的結點
     * @param index:
     * @return：int
     */
    public int remove(int index){
        if (index<0||index>=size){
            throw new ArrayIndexOutOfBoundsException("删除元素位置不合法");
        }
        ListNode pre=null;
        ListNode cur=head;
        for (int i = 0; i <index ; i++) {// 找到待删除結點
            pre=cur;
            cur=cur.next;
        }
        int res=cur.val;
        ListNode next=cur.next;// 待删除元素的下一個節點
        if (pre==null) {//待删除結點為頭結點
            cur.next=null;
            head=next;
        }else{
            pre.next=next;
        }
        size--;//元素數量減1
        return res;
    }
    /***
     * @函數功能：周遊連結清單
     * @param head:
     * @return：void
     */
    public void print(ListNode head){
        if (head==null){
            System.out.println("NULL");
            return;
        }
        ListNode cur=head;
        System.out.print(cur.val);
        cur=cur.next;
        while(cur!=null){
            System.out.print("->"+cur.val);
            cur=cur.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        LinkList linkList=new LinkList();
        System.out.println(linkList.getSize());
        linkList.insert(1,0);
        System.out.println(linkList.getSize());
        linkList.insert(2,0);
        System.out.println(linkList.getSize());
        linkList.print(linkList.head);
        linkList.remove(1);
        linkList.print(linkList.head);
        linkList.remove(0);
        linkList.print(linkList.head);
    }
}