LinkedList 方法详解

通过阅读LinkedList的api, 自己用代码实现他的常用方法;

import java.util.List;

public class MyLinkedList {
    //链表的首地址
    private Node first = null;
    //尾节点
    private Node last = null;
    //记录链表的有效长度
    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;
        }
        //创建新节点
        Node node = new Node();
        node.data = element;
        node.next = null;
        //链表为空
        if (this.last == null) {
            this.first = node;
            this.last = node;
        }else {
            //链表不为空
            //开头添加
            if (index == 0) {
                this.addFirst(element);
            }else if (index == size) {
                //尾部添加
                this.addLast(element);
            }else {
                //中间添加
                Node preNode = this.node(index - 1);
                //开始preNode的next指的是indexNode
                Node indexNode = preNode.next;
                node.next = indexNode;
                preNode.next = node; 
                this.size++;
            }
        }
    }
    
    //根据下标找节点
    private Node node(int index) {
        //判断index
        if (index < 0 || index >= size) {
            return null;
        }
        //设置一个循环标记
        int tag = 0;
        //先给一个空节点
        Node temp = null;
        for (Node l = first; l != null; l = l.next) {
            //找到下标
            if (tag == index) {
                //将l赋给temp
                temp = l;
                break;
            }
            tag++;
        }
        return temp;
    }
    
    //根据下标找元素
    public Object get(int index) {
        //判断index
        if (index < 0 || index >= size) {
            return null;
        }
        //根据下标找到节点的元素
        //调用node方法
        return this.node(index).data;
    }
    
    //在头部添加  (将指定元素插入到此列表的头部)
    public void addFirst(Object o) {
        //创建新节点
        Node node = new Node();
        node.data = o;
        node.next = null;   // 不写默认就是空
        if (this.last == null) {   //链表为空
            //链表中一个元素都没有.直接将新的节点设置成头节点,头节点和尾节点是一样的
            this.first = node;
            this.last = node;
        }else {     //链表不为空
            //链表中有元素
            //让新节点的地址指向原来的first,这样就变成头节点了
            node.next = first;
            //然后把新的节点设置成头节点
            this.first = node;
        }
        this.size++;
    }
    //在尾部添加  (将指定元素插入到此列表的尾部)
    public void addLast(Object o) {
        Node node = new Node();
        node.data = o;
        node.next = null;  
        
        //一个元素都没有
        if (this.last == null) {
            this.first = node;
            this.last = node;
        }else {
            //有元素
            this.last.next = node;
            this.last = node;
        }
        this.size++;
    }
    //返回链表的长度
    public int size() {
        return this.size;
    }
    
    //构造方法
    public MyLinkedList() {
        
    }
    //构造一个包含指定List中的元素的列表
    public MyLinkedList(List list) {
        
    }
    
    //循环
    @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号元素到他的长度减一个位置,不要最后的逗号
            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;
        }
        //根据index查找节点
        Node node = this.node(index);
        //记录原来的值
        Object temp = node.data;
        //修改元素
        node.data = element;
        return temp;    //返回修改前的记录
    }
    
    //删除节点  (根据下标移除节点)
    public Object remove(int index) {
        if (index < 0 || index >= size) {
            return null;
        }
        Node temp = null;     //定义临时变量接收要删除的值
        //只有一个节点的时候
        if (this.size == 1) {
            temp = this.first;   //记录要删除的节点
            this.first = null;
            this.last = null;
        }//两个节点及以上,且不是删除首节点
        else if(index != 0) {
            //根据下标找到节点(如果有多个元素)
            //比如有三个节点,我们要删除第二个,先找到第一个,然后将第一个节点的地址设置成要删除的节点的地址
            Node preNode = this.node(index - 1);
            //preNode.next指向的是他后边的节点,赋给node
            Node node = preNode.next;
            temp = node;    //记录要删除的节点
            preNode.next = node.next;
        }else {    //两个节点及以上,且删除首节点
            temp = this.first;    //记录要删除的节点
            //如果删除第一个元素;将第一个元素指向的地址设置成首地址就可以
            this.first = this.first.next;
        }
        this.size--;
        return temp.data;   //返回要删除的元素
    }
    
    //是否包含某元素
    public boolean contain(Object o) {
        return indexOf(o) != -1;
    }
    
    //根据元素返回下标
    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;    //找不到元素
    }
    
}

//节点
class Node {
    Object data;   //存数据
    Node next;    //下个节点的引用   类似于:  (Person p = new Person();)
}