Android(安卓)LinkedList

LinkedList实现

Android的LinkedList是通过双向列表实现的。链表元素除了含有自身的值以为，还含有上一个元素和下一个元素的引用。

    private static final class Link {        ET data;//当前值        Link previous, next;//上一个，和下个链表对象的引用        Link(ET o, Link p, Link n) {            data = o;            previous = p;            next = n;        }    }

普通添加方法

真正是由该方法实现，新元素添加在链表的最后，addLast同样是这个方法实现
将上一个元素的head节点指向新元素

 private boolean addLastImpl(E object) {        Link oldLast = voidLink.previous;      //新元素的头指向上一个元素，尾指向链表的头部        Link newLink = new Link(object, oldLast, voidLink);      //头元素的头指向新元素        voidLink.previous = newLink;       //上一个结尾元素的尾 指向新元素        oldLast.next = newLink;        size++;        modCount++;        return true;    }

2.在指定位置插入
1.插入的位置要下于link链表的长度
2.向前后移动元数据，空出当前位置给新元素，上一个元素的next和下一个元素的head分别指向这个元素。

  public void add(int location, E object) {        if (location >= 0 && location <= size) {            Link link = voidLink;            if (location < (size / 2)) {                for (int i = 0; i <= location; i++) {                    link = link.next;                }            } else {                for (int i = size; i > location; i--) {                    link = link.previous;                }            }            Link previous = link.previous;            Link newLink = new Link(object, previous, link);            previous.next = newLink;            link.previous = newLink;            size++;            modCount++;        } else {            throw new IndexOutOfBoundsException();        }    }

查询

从头开始遍历链表元素的每一个元素。

 public boolean contains(Object object) {        Link link = voidLink.next;        if (object != null) {            while (link != voidLink) {                if (object.equals(link.data)) {                    return true;                }                link = link.next;            }        } else {            while (link != voidLink) {                if (link.data == null) {                    return true;                }                link = link.next;            }        }        return false;    }

删除

同样会遍历元素找到对应位置上前后的元素，将之前该位置前后的连个元素链接首位链接起来。

    @Override    public E remove(int location) {        if (location >= 0 && location < size) {            Link link = voidLink;            if (location < (size / 2)) {                for (int i = 0; i <= location; i++) {                    link = link.next;                }            } else {                for (int i = size; i > location; i--) {                    link = link.previous;                }            }            Link previous = link.previous;            Link next = link.next;            previous.next = next;            next.previous = previous;            size--;            modCount++;            return link.data;        }        throw new IndexOutOfBoundsException();    }

LinkedList实现

普通添加方法

查询

删除

更多相关文章

随机推荐