通過(guò)閱讀LinkedList的api, 自己用代碼實(shí)現(xiàn)他的常用方法;

import java.util.List;

public class MyLinkedList {
    //鏈表的首地址
    private Node first = null;
    //尾節(jié)點(diǎn)
    private Node last = null;
    //記錄鏈表的有效長(zhǎng)度
    private int size = 0;
    
    //往鏈表中添加元素  (在尾部)
    public boolean add(Object o) {
        this.addLast(o);
        return true;
    }
    //在此列表中指定的位置插入指定的元素
    public void add(int index,Object element) {
        //index越界判斷
        if (index < 0 || index > size) {
            return;
        }
        //創(chuàng)建新節(jié)點(diǎn)
        Node node = new Node();
        node.data = element;
        node.next = null;
        //鏈表為空
        if (this.last == null) {
            this.first = node;
            this.last = node;
        }else {
            //鏈表不為空
            //開(kāi)頭添加
            if (index == 0) {
                this.addFirst(element);
            }else if (index == size) {
                //尾部添加
                this.addLast(element);
            }else {
                //中間添加
                Node preNode = this.node(index - 1);
                //開(kāi)始preNode的next指的是indexNode
                Node indexNode = preNode.next;
                node.next = indexNode;
                preNode.next = node; 
                this.size++;
            }
        }
    }
    
    //根據(jù)下標(biāo)找節(jié)點(diǎn)
    private Node node(int index) {
        //判斷index
        if (index < 0 || index >= size) {
            return null;
        }
        //設(shè)置一個(gè)循環(huán)標(biāo)記
        int tag = 0;
        //先給一個(gè)空節(jié)點(diǎn)
        Node temp = null;
        for (Node l = first; l != null; l = l.next) {
            //找到下標(biāo)
            if (tag == index) {
                //將l賦給temp
                temp = l;
                break;
            }
            tag++;
        }
        return temp;
    }
    
    //根據(jù)下標(biāo)找元素
    public Object get(int index) {
        //判斷index
        if (index < 0 || index >= size) {
            return null;
        }
        //根據(jù)下標(biāo)找到節(jié)點(diǎn)的元素
        //調(diào)用node方法
        return this.node(index).data;
    }
    
    //在頭部添加  (將指定元素插入到此列表的頭部)
    public void addFirst(Object o) {
        //創(chuàng)建新節(jié)點(diǎn)
        Node node = new Node();
        node.data = o;
        node.next = null;   // 不寫(xiě)默認(rèn)就是空
        if (this.last == null) {   //鏈表為空
            //鏈表中一個(gè)元素都沒(méi)有.直接將新的節(jié)點(diǎn)設(shè)置成頭節(jié)點(diǎn),頭節(jié)點(diǎn)和尾節(jié)點(diǎn)是一樣的
            this.first = node;
            this.last = node;
        }else {     //鏈表不為空
            //鏈表中有元素
            //讓新節(jié)點(diǎn)的地址指向原來(lái)的first,這樣就變成頭節(jié)點(diǎn)了
            node.next = first;
            //然后把新的節(jié)點(diǎn)設(shè)置成頭節(jié)點(diǎn)
            this.first = node;
        }
        this.size++;
    }
    //在尾部添加  (將指定元素插入到此列表的尾部)
    public void addLast(Object o) {
        Node node = new Node();
        node.data = o;
        node.next = null;  
        
        //一個(gè)元素都沒(méi)有
        if (this.last == null) {
            this.first = node;
            this.last = node;
        }else {
            //有元素
            this.last.next = node;
            this.last = node;
        }
        this.size++;
    }
    //返回鏈表的長(zhǎng)度
    public int size() {
        return this.size;
    }
    
    //構(gòu)造方法
    public MyLinkedList() {
        
    }
    //構(gòu)造一個(gè)包含指定List中的元素的列表
    public MyLinkedList(List list) {
        
    }
    
    //循環(huán)
    @Override
    public String toString() {
        String string = "[";
        //鏈表的遍歷
        for (Node l = first; l != null; l = l.next) {
            Object object = l.data;
            string = string + object.toString();
            string = string + ",";
        }
        if (string.length() >= 2) {
            //裁剪字符串,從0號(hào)元素到他的長(zhǎng)度減一個(gè)位置,不要最后的逗號(hào)
            string = string.substring(0, string.length() - 1);
        }
        string += "]";
        return string;
        
    }
    
    //修改元素
    public Object set(int index,Object element) {
        //判斷index的范圍
        if (index < 0 || index >= size) {
             return null;
        }
        //根據(jù)index查找節(jié)點(diǎn)
        Node node = this.node(index);
        //記錄原來(lái)的值
        Object temp = node.data;
        //修改元素
        node.data = element;
        return temp;    //返回修改前的記錄
    }
    
    //刪除節(jié)點(diǎn)  (根據(jù)下標(biāo)移除節(jié)點(diǎn))
    public Object remove(int index) {
        if (index < 0 || index >= size) {
            return null;
        }
        Node temp = null;     //定義臨時(shí)變量接收要?jiǎng)h除的值
        //只有一個(gè)節(jié)點(diǎn)的時(shí)候
        if (this.size == 1) {
            temp = this.first;   //記錄要?jiǎng)h除的節(jié)點(diǎn)
            this.first = null;
            this.last = null;
        }//兩個(gè)節(jié)點(diǎn)及以上,且不是刪除首節(jié)點(diǎn)
        else if(index != 0) {
            //根據(jù)下標(biāo)找到節(jié)點(diǎn)(如果有多個(gè)元素)
            //比如有三個(gè)節(jié)點(diǎn),我們要?jiǎng)h除第二個(gè),先找到第一個(gè),然后將第一個(gè)節(jié)點(diǎn)的地址設(shè)置成要?jiǎng)h除的節(jié)點(diǎn)的地址
            Node preNode = this.node(index - 1);
            //preNode.next指向的是他后邊的節(jié)點(diǎn),賦給node
            Node node = preNode.next;
            temp = node;    //記錄要?jiǎng)h除的節(jié)點(diǎn)
            preNode.next = node.next;
        }else {    //兩個(gè)節(jié)點(diǎn)及以上,且刪除首節(jié)點(diǎn)
            temp = this.first;    //記錄要?jiǎng)h除的節(jié)點(diǎn)
            //如果刪除第一個(gè)元素;將第一個(gè)元素指向的地址設(shè)置成首地址就可以
            this.first = this.first.next;
        }
        this.size--;
        return temp.data;   //返回要?jiǎng)h除的元素
    }
    
    //是否包含某元素
    public boolean contain(Object o) {
        return indexOf(o) != -1;
    }
    
    //根據(jù)元素返回下標(biāo)
    public int indexOf(Object o) {
        int index = 0;
        if (o == null) {
            for (Node l = first; l != null; l = l.next) {
                if (l.data == null) {
                    return index;
                }
                index++;
            }
        }else {
            for (Node l = first; l != null; l = l.next) {
                if (o.equals(l.data)) {
                    return index;
                }
                index++;
            }
        }
        return -1;    //找不到元素
    }
    
}

//節(jié)點(diǎn)
class Node {
    Object data;   //存數(shù)據(jù)
    Node next;    //下個(gè)節(jié)點(diǎn)的引用   類(lèi)似于:  (Person p = new Person();)
}