• LinkedList是基于链表实现的(双向链表)
private static class Node<E> {
        E item;
        Node<E> next;
        Node<E> prev;
        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }
  • LinkedList是否允许空:允许
  • LinkedList是否允许重复数据:运行
  • LinkedList是否有序:有序
  • LinkedList是否线程安全:非线程安全
  • LinkedList 是没有初始化链表大小的构造函数,因为链表不像数组,一个定义好的数组是必须要有确定的大小,然后去分配内存空间,而链表不一样,它没有确定的大小,通过指针的移动来指向下一个内存地址的分配
  • 添加方法

将元素添加到链表头:

public void addFirst(E e) {
        linkFirst(e);
}
private void linkFirst(E e) {
        final Node<E> f = first;// 将头节点赋值给 f
        final Node<E> newNode = new Node<>(null, e, f);
        first = newNode; //将新节点设为头节点,那么原先的头节点 f 变为第二个节点
        if (f == null)
            last = newNode;
        else
            f.prev = newNode; //将原先的头节点的上一个节点指向新节点
        size++;
        modCount++;
    }

将元素添加链表尾:

public void addLast(E e) {
        linkLast(e);
}
void linkLast(E e) {
        final Node<E> l = last; //将l设为尾节点
        final Node<E> newNode = new Node<>(l, e, null);
        last = newNode;
        if (l == null)
            first = newNode;
        else
            l.next = newNode; //将原来尾节点下一个节点的引用指向新节点
        size++;
        modCount++;
    }
  • 插入方法
public void add(int index, E element) {
        checkPositionIndex(index);
        if (index == size)
            linkLast(element);
        else
            linkBefore(element, node(index));
}
void linkBefore(E e, Node<E> succ) {
        // assert succ != null;
        final Node<E> pred = succ.prev; //将pred设为插入节点的上一个节点
        final Node<E> newNode = new Node<>(pred, e, succ); //将新节点的上引用设为pred,下引用设为succ
        succ.prev = newNode; //succ的上一个节点的引用设为新节点
        if (pred == null)
            first = newNode;
        else
            pred.next = newNode; //插入节点的下一个节点引用设为新节点
        size++;
        modCount++;
    }
  • 删除方法
public E remove(int index) {
        checkElementIndex(index);
        return unlink(node(index));
}

 

E unlink(Node<E> x) {
        // assert x != null;
        final E element = x.item;
        final Node<E> next = x.next;
        final Node<E> prev = x.prev;
        if (prev == null) {
            first = next;
        } else {
            prev.next = next; //将删除节点的上一个节点的下一个节点引用指向删除节点的下一个节点(去掉删除节点)
            x.prev = null;
        }
        if (next == null) {
            last = prev;
        } else {
            next.prev = prev; //将删除节点的下一个节点的上一个节点的引用指向删除节点的上一个节点
            x.next = null;
        }
        x.item = null; //删除节点内容置为null,便于垃圾回收
        size--;
        modCount++;
        return element;
    }
  • 修改方法
public E set(int index, E element) {
        checkElementIndex(index);
        Node<E> x = node(index);
        E oldVal = x.item;
        x.item = element;
        return oldVal; //返回指定索引位置原来的元素
}
  • 查找方法
public E get(int index) {
        checkElementIndex(index);
        return node(index).item;
}
  • 遍历方法

普通 for 循环:

LinkedList<String> linkedList = new LinkedList<>();
linkedList.add("A");
linkedList.add("B");
linkedList.add("C");
linkedList.add("D");
for(int i = 0 ; i < linkedList.size() ; i++){
    System.out.print(linkedList.get(i)+" ");//A B C D
}

迭代器:

LinkedList<String> linkedList = new LinkedList<>();
linkedList.add("A");
linkedList.add("B");
linkedList.add("C");
linkedList.add("D");
Iterator<String> listIt = linkedList.listIterator();
while(listIt.hasNext()){
    System.out.print(listIt.next()+" ");//A B C D
}

//通过适配器模式实现的接口,作用是倒叙打印链表
Iterator<String> it = linkedList.descendingIterator();
while(it.hasNext()){
    System.out.print(it.next()+" ");//D C B A
}

foreach 循环:

LinkedList<String> linkedList = new LinkedList<>();
linkedList.add("A");
linkedList.add("B");
linkedList.add("C");
linkedList.add("D");
for(String str : linkedList){
    System.out.print(str + "");
}
  • 如果使用普通for循环遍历LinkedList,在大数据量的情况下,其遍历速度将非常非常慢,因为每次遍历一个索引的元素之前,都要访问之间所有的索引

 

Leave a comment

电子邮件地址不会被公开。 必填项已用*标注