实现自定义的 LinkedList

---

1.实现思路：通过双链表来实现，并且保留该表两端的引用。

2.实现设计：

---

a. MyLinkedList类：包含到两端的链，表的大小以及一些方法。
b. Node类：一个节点包含数据以及前一个节点的链和下一个节点的链，以及其构造方法。
c. LinkedListIterator类：实现接口Iterator，提供next，hasNext，remove方法的实现。

---

3. 具体实现过程---Coding：

---

a. 实现Node类：

//定义节点，类型为AnyType
    private static class Node<AnyType>{
        //通过构造函数，创建一个节点
        public Node(AnyType d, Node<AnyType> p, Node<AnyType> n){
            data = d;
            prev = p;
            next = n;
        }
        //当前结点数据
        public AnyType data;
        //向前驱点
        public Node<AnyType> prev;
        //向后驱点
        public Node<AnyType> next;
    }

b. 定义一些常量：

public class MyLinkedList<Object> implements Iterable<Object> {
    //定义当前长度
    private int theSize;
    //定义操作次数，增加，删除等影响结构的操作
    private int modCount = 0;
    //定义开始标记
    private Node<Object> beginMarker;
    //定义结束标记
    private Node<Object> endMarker;
}

c.构造函数以及初始化操作：

//创建时，清空所有之前的数据
    public MyLinkedList(){
        doClear();
    }

    //清空操作
    public void clear(){
        doClear();
    }

    //实现具体的清空操作
    public void doClear() {
        //定义开始节点
        beginMarker = new Node<Object>(null,null,null);
        //定义结束节点，注意这里将开始节点作为结束节点的向前节点
        endMarker = new Node<Object>(null, beginMarker, null);
        //将结束节点作为开始节点的向后节点
        beginMarker.next = endMarker;
        //初始化大小为0
        theSize = 0;
        //操作加1
        modCount ++;
    }

    //返回当前长度
    public int size(){
        return theSize;
    }

    //判断当前链表是否为空
    public boolean isEmpty(){
        return theSize == 0;
    }

d. get操作，获取到节点以及节点数据等

    /**
     * 根据链表位置获取到对应的数据：通过调用getNode方法获取到当前结点，
     * 再获取到当前结点的数据
     * @param idx 传入的位置
     * @return
     */
    public Object get(int idx){
        return getNode(idx).data;
    }

    /**
     * 获取到对应位置的节点：调用具体的getNode方法去获取
     * @param idx
     * @return
     */
    private Node<Object> getNode(int idx){
        return getNode(idx, 0 , size());
    }

    /**
     * 实现根据位置获取到节点
     * @param idx 当前位置
     * @param lower 开始位置
     * @param upper 结束位置
     * @return
     */
    private Node<Object> getNode(int idx, int lower, int upper){
        //定义一个临时节点
        Node<Object> p;
        //若传入的位置超出范围，则抛出异常
        if (idx < lower || idx > upper)
            throw new IndexOutOfBoundsException();
        //若当前位置在左边，则从开始出进行向后遍历
        if (idx < size() / 2){
            //移动到开始处
            p = beginMarker;
            //遍历直到到达所要求的位置
            for (int i = 0; i < idx; i ++){
                p = p.next;
            }
        }
        //若当前位置在右边，则从尾部开始进行向前遍历
        else {
            p = endMarker;
            for (int i = size(); i > idx; i --){
                p = p.prev;
            }
        }
        return p;
    }

e. set操作，用于更新节点数据：

    /**
     * 更新数据操作
     * @param idx 传入的链表位置
     * @param newVal 更新的数据
     * @return
     */
    public Object set(int idx, Object newVal){
        //获取到对应位置的节点
        Node<Object> p = getNode(idx);
        //获取到当前数据
        Object oldVal = p.data;
        p.data = newVal;
        //返回原来的数据
        return oldVal;
    }

f. 添加操作：主要理解addBefore操作

    /**
     * 实现默认方式添加元素
     * @param x
     * @return
     */
    public boolean add(Object x){
        //调用add方法，添加到尾部
        add(size(), x);
        return true;
    }

    /**
     * 实现添加到具体的某个位置中
     * @param idx
     * @param x
     */
    public void add(int idx, Object x) {
        addBefore(getNode(idx), x);
    }

    /**
     * 实现具体的添加操作
     * @param p 当前位置的节点
     * @param x 节点数据
     */
    private void addBefore(Node<Object> p , Object x){
        //根据p节点创建一个新的节点
        Node<Object> newNode = new Node<Object>(x, p.prev, p);
        //连接新节点与前后两个节点
        newNode.prev.next = newNode;
        p.prev = newNode;
        //长度和操作次数++
        theSize ++;
        modCount ++;
    }

添加操作示意图：

add_node

 //实际上，通过构造函数，便完成了示意图中的1和2操作
 Node<Object> newNode = new Node<Object>(x, p.prev, p);
 //实现了操作3
 newNode.prev.next = newNode;
 //实现了操作4
 p.prev = newNode;

g. 实现删除节点操作：

    /**
     * 实现移除某个位置的节点
     * @param idx
     * @return
     */
    public Object remove(int idx){
        return remove(getNode(idx));
    }

    /**
     * 具体移除节点操作
     * @param p 传入要移除的节点
     * @return
     */
    private Object remove(Node<Object> p){
        //移除当前节点
        p.next.prev = p.prev;
        p.prev.next = p.next;
        //长度--
        theSize --;
        //操作次数++
        modCount ++;
        //返回移除节点的数据
        return p.data;
    }

删除示意图：

delete_node.png

h. 实现查找元素位置操作：

/**
     * 实现查找链表中首先出现的元素位置
     * @param x
     * @return
     */
    public int indexOf(Object x){
        int index = 0;
        //若传入的数据为空
        if (x == null){
            //遍历链表，查找是否含有数据为null的节点，找到后立即返回当前位置
            for (Node<Object> node = beginMarker.next; node != endMarker; node = node.next){
                if (node.data == null){
                    return index;
                }
                index ++;
            }
        }
        //数据不为空时，使用equals方法进行比较
        else {
            for (Node<Object> node = beginMarker.next; node != endMarker; node = node.next){
                if (x.equals(node.data)){
                    return index;
                }
                index ++;
            }
        }
        return -1;
    }

    /**
     * 实现查找链表中元素最后出现的位置
     * 从尾节点开始向前遍历搜查
     * @param x
     * @return
     */
    public int lastIndexOf(Object x){
        int index = size() - 1;
        if (x == null){
            for (Node<Object> node = endMarker.prev; node != beginMarker; node = node.prev){
                if (node.data == null){
                    return index;
                }
                index --;
            }
        } else {
            for (Node<Object> node = endMarker.prev; node != beginMarker; node = node.prev){
                if (x.equals(node.data)){
                    return index;
                }
                index --;
            }
        }
        return -1;
    }

i. 实现LinkedListIterator类：

private class LinkedListIterator implements Iterator<Object>{
        //定义当前结点为始节点的下一个节点
        private Node<Object> current = beginMarker.next;
        //定义操作次数
        private int expectedModCount = modCount;
        //判断是否可以进行删除
        private boolean okToRemove = false;

        //判断是否存在下一个节点
        @Override
        public boolean hasNext() {
            return current != endMarker;
        }

        //获取到下一个节点数据
        @Override
        public Object next() {
            //操作次数不一致抛出异常
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            //不存在下一个节点，抛出异常
            if (!hasNext())
                throw new NoSuchElementException();
            //获取到下一个节点的数据，并设置okToRemove为true，表示可以进行删除
            Object nextItem = current.data;
            current = current.next;
            okToRemove = true;
            return nextItem;
        }

        //进行删除操作
        public void remove(){
            //操作次数不一致，抛出异常
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            //无法进行删除操作，必须先进行next，才可以进行remove操作
            if (!okToRemove)
                throw new IllegalStateException();
            //调用链表中的remove方法进行删除操作，注意传入的是current.pre节点
            MyLinkedList.this.remove(current.prev);
            //操作次数++
            expectedModCount ++;
            okToRemove = false;
        }
    }

完整代码如下：

/**
 * Created by Administrator on 2017/3/5/005.
 * 实现自定义LinkedList
 */
public class MyLinkedList<Object> implements Iterable<Object> {
    //定义当前长度
    private int theSize;
    //定义操作次数，增加，删除等影响结构的操作
    private int modCount = 0;
    //定义开始标记
    private Node<Object> beginMarker;
    //定义结束标记
    private Node<Object> endMarker;

    //定义节点，类型为AnyType
    private static class Node<AnyType>{
        //通过构造函数，创建一个节点
        public Node(AnyType d, Node<AnyType> p, Node<AnyType> n){
            data = d;
            prev = p;
            next = n;
        }
        //当前结点数据
        public AnyType data;
        //向前驱点
        public Node<AnyType> prev;
        //向后驱点
        public Node<AnyType> next;
    }

    //创建时，清空所有之前的数据
    public MyLinkedList(){
        doClear();
    }

    //清空操作
    public void clear(){
        doClear();
    }

    //实现具体的清空操作
    public void doClear() {
        //定义开始节点
        beginMarker = new Node<Object>(null,null,null);
        //定义结束节点，注意这里将开始节点作为结束节点的向前节点
        endMarker = new Node<Object>(null, beginMarker, null);
        //将结束节点作为开始节点的向后节点
        beginMarker.next = endMarker;
        //初始化大小为0
        theSize = 0;
        //操作加1
        modCount ++;
    }

    //返回当前长度
    public int size(){
        return theSize;
    }

    //判断当前链表是否为空
    public boolean isEmpty(){
        return theSize == 0;
    }

    /**
     * 根据链表位置获取到对应的数据：通过调用getNode方法获取到当前结点，
     * 再获取到当前结点的数据
     * @param idx 传入的位置
     * @return
     */
    public Object get(int idx){
        return getNode(idx).data;
    }

    /**
     * 更新数据操作
     * @param idx 传入的链表位置
     * @param newVal 更新的数据
     * @return
     */
    public Object set(int idx, Object newVal){
        //获取到对应位置的节点
        Node<Object> p = getNode(idx);
        //获取到当前数据
        Object oldVal = p.data;
        p.data = newVal;
        //返回原来的数据
        return oldVal;
    }

    /**
     * 获取到对应位置的节点：调用具体的getNode方法去获取
     * @param idx
     * @return
     */
    private Node<Object> getNode(int idx){
        return getNode(idx, 0 , size());
    }

    /**
     * 实现根据位置获取到节点
     * @param idx 当前位置
     * @param lower 开始位置
     * @param upper 结束位置
     * @return
     */
    private Node<Object> getNode(int idx, int lower, int upper){
        //定义一个临时节点
        Node<Object> p;
        //若传入的位置超出范围，则抛出异常
        if (idx < lower || idx > upper)
            throw new IndexOutOfBoundsException();
        //若当前位置在左边，则从开始出进行向后遍历
        if (idx < size() / 2){
            //移动到开始处
            p = beginMarker;
            //遍历直到到达所要求的位置
            for (int i = 0; i < idx; i ++){
                p = p.next;
            }
        }
        //若当前位置在右边，则从尾部开始进行向前遍历
        else {
            p = endMarker;
            for (int i = size(); i > idx; i --){
                p = p.prev;
            }
        }
        return p;
    }

    /**
     * 实现默认方式添加元素
     * @param x
     * @return
     */
    public boolean add(Object x){
        //调用add方法，添加到尾部
        add(size(), x);
        return true;
    }

    /**
     * 实现添加到具体的某个位置中
     * @param idx
     * @param x
     */
    public void add(int idx, Object x) {
        addBefore(getNode(idx), x);
    }

    /**
     * 实现具体的添加操作
     * @param p 当前位置的节点
     * @param x 节点数据
     */
    private void addBefore(Node<Object> p , Object x){
        //实际上，通过构造函数，便完成了示意图中的1和2操作
        Node<Object> newNode = new Node<Object>(x, p.prev, p);
        //实现了操作3
        newNode.prev.next = newNode;
        //实现了操作4
        p.prev = newNode;
        //长度和操作次数++
        theSize ++;
        modCount ++;
    }

    /**
     * 实现移除某个位置的节点
     * @param idx
     * @return
     */
    public Object remove(int idx){
        return remove(getNode(idx));
    }

    /**
     * 具体移除节点操作
     * @param p 传入要移除的节点
     * @return
     */
    private Object remove(Node<Object> p){
        //移除当前节点
        p.next.prev = p.prev;
        p.prev.next = p.next;
        //长度--
        theSize --;
        //操作次数++
        modCount ++;
        //返回移除节点的数据
        return p.data;
    }

    /**
     * 获取到第一个节点数据
     * @return
     */
    public Object getFirst(){
        //先判断链表是否为空，为空则抛出异常
        if (isEmpty()){
            throw new NoSuchElementException();
        }
        return beginMarker.next.data;
    }

    //获取到链表中的最后一个节点数据
    public Object getLast(){
        if (isEmpty()){
            throw new NoSuchElementException();
        }
        return endMarker.prev.data;
    }

    //移除链表中第一个节点
    public Object removeFirst(){
        if (isEmpty()){
            throw new NoSuchElementException();
        }
        //调用remove方法，移除开始节点的下一个节点即可
        return remove(beginMarker.next);
    }

    //移除链表中的最后一个节点
    public Object removeLast(){
        if (isEmpty()){
            throw new NoSuchElementException();
        }
        //调用remove方法，移除结束节点的上一个节点即可
        return remove(endMarker.prev);
    }

    //从头部开始添加节点
    public void addFirst(Object x){
        //将添加节点设置为头节点即可
        addBefore(beginMarker.next, x);
    }

    //从尾部添加节点
    public void addLast(Object x){
        add(x);
    }

    //添加一个Collection集合
    public void addAll(Collection<Object> collection){
        //添加集合为空，则抛出异常
        if (collection == null){
            throw new NullPointerException();
        }
        //遍历集合，并逐个添加到链表中
        for (Object aCollection : collection) {
            add(aCollection);
        }
    }

    //判断链表中是否含有某个元素，调用indexOf方法即可
    public boolean contains(Object x){
        return indexOf(x) != -1;
    }

    /**
     * 实现查找链表中首先出现的元素位置
     * @param x
     * @return
     */
    public int indexOf(Object x){
        int index = 0;
        //若传入的数据为空
        if (x == null){
            //遍历链表，查找是否含有数据为null的节点，找到后立即返回当前位置
            for (Node<Object> node = beginMarker.next; node != endMarker; node = node.next){
                if (node.data == null){
                    return index;
                }
                index ++;
            }
        }
        //数据不为空时，使用equals方法进行比较
        else {
            for (Node<Object> node = beginMarker.next; node != endMarker; node = node.next){
                if (x.equals(node.data)){
                    return index;
                }
                index ++;
            }
        }
        return -1;
    }

    /**
     * 实现查找链表中元素最后出现的位置
     * 从尾节点开始向前遍历搜查
     * @param x
     * @return
     */
    public int lastIndexOf(Object x){
        int index = size() - 1;
        if (x == null){
            for (Node<Object> node = endMarker.prev; node != beginMarker; node = node.prev){
                if (node.data == null){
                    return index;
                }
                index --;
            }
        } else {
            for (Node<Object> node = endMarker.prev; node != beginMarker; node = node.prev){
                if (x.equals(node.data)){
                    return index;
                }
                index --;
            }
        }
        return -1;
    }

    /**
     * 实现链表的遍历
     * @return
     */
    public Iterator<Object> iterator(){
        return new LinkedListIterator();
    }

    private class LinkedListIterator implements Iterator<Object>{
        //定义当前结点为始节点的下一个节点
        private Node<Object> current = beginMarker.next;
        //定义操作次数
        private int expectedModCount = modCount;
        //判断是否可以进行删除
        private boolean okToRemove = false;

        //判断是否存在下一个节点
        @Override
        public boolean hasNext() {
            return current != endMarker;
        }

        //获取到下一个节点数据
        @Override
        public Object next() {
            //操作次数不一致抛出异常
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            //不存在下一个节点，抛出异常
            if (!hasNext())
                throw new NoSuchElementException();
            //获取到下一个节点的数据，并设置okToRemove为true，表示可以进行删除
            Object nextItem = current.data;
            current = current.next;
            okToRemove = true;
            return nextItem;
        }

        //进行删除操作
        public void remove(){
            //操作次数不一致，抛出异常
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            //无法进行删除操作，必须先进行next，才可以进行remove操作
            if (!okToRemove)
                throw new IllegalStateException();
            //调用链表中的remove方法进行删除操作，注意传入的是current.pre节点
            MyLinkedList.this.remove(current.prev);
            //操作次数++
            expectedModCount ++;
            okToRemove = false;
        }
    }
}

测试代码：

public class LinkedListTest {

    public static void main(String[] args){
        //进行添加操作
        MyLinkedList<String> myLinkedList = new MyLinkedList<>();
        myLinkedList.add("Java");
        myLinkedList.add("C++");
        myLinkedList.add("Python");
        myLinkedList.add(2, "PHP");
        //遍历结果
        printLinkedList(myLinkedList.iterator());

        //进行删除和更新操作
        myLinkedList.remove(2);
        myLinkedList.set(1,"JavaScript");
        printLinkedList(myLinkedList.iterator());

        //获取到首尾元素
        System.out.println("first data : " + myLinkedList.getFirst());
        System.out.println("last data : " + myLinkedList.getLast());

        //移除首尾节点
        myLinkedList.removeFirst();
        myLinkedList.removeLast();
        printLinkedList(myLinkedList.iterator());

        //分别从首尾部添加
        myLinkedList.addFirst("C#");
        myLinkedList.addLast("CSS");
        printLinkedList(myLinkedList.iterator());

        //清空操作
        myLinkedList.clear();
        printLinkedList(myLinkedList.iterator());

        //addAll方法
        List<String> list = new ArrayList<>();
        list.add("JAVA");
        list.add("C++");
        list.add("C");
        list.add("JavaScript");
        list.add("C");
        list.add("HTML");
        myLinkedList.addAll(list);
        printLinkedList(myLinkedList.iterator());

        //查找元素
        System.out.println("是否存在CSS教程: " + myLinkedList.contains("CSS"));
        System.out.println("是否存在HTML教程: " + myLinkedList.contains("HTML"));
        System.out.println("C教程开始的位置为: " + myLinkedList.indexOf("C"));
        System.out.println("C教程最后的位置为: " + myLinkedList.lastIndexOf("C"));
    }

    private static void printLinkedList(Iterator<String> iterator){
        System.out.print("当前链表为: ");
        while (iterator.hasNext()){
            System.out.print(iterator.next() + " ");
        }
        System.out.println();
    }
}

输出结果：

当前链表为: Java C++ PHP Python 
当前链表为: Java JavaScript Python 
first data : Java
last data : Python
当前链表为: JavaScript 
当前链表为: C# JavaScript CSS 
当前链表为: 
当前链表为: JAVA C++ C JavaScript C HTML 
是否存在CSS教程: false
是否存在HTML教程: true
C教程开始的位置为: 2
C教程最后的位置为: 4