JAVA中LinkedList的基本方法

古城微笑少年丶 2023-07-17 07:25 112阅读 0赞

java中LinkedList是一个链表

LinkedList可以存储null值,如下，我们存储了四个单词和一个null,我们尝试输出，可以看到最后一个是输出null

int i=0;
            LinkedList<String> linkedList=new LinkedList<>();
            linkedList.add("Java");
            linkedList.add("PHP");
            linkedList.add("go");
            linkedList.add("c++");
            linkedList.add(null);
            while( i<linkedList.size()){
                System.out.println(linkedList.get(i));
                i++;
            }

Java
    PHP
    go
    c++
    null

## 删除元素 ##

我们通过源码可以看到，LinkedList中有remove方法，而且是重载，可以传值，也可以不传

1.传值情况

public boolean remove(Object o) {
            if (o == null) {
                for (Node<E> x = first; x != null; x = x.next) {
                    if (x.item == null) {
                        unlink(x);
                        return true;
                    }
                }
            } else {
                for (Node<E> x = first; x != null; x = x.next) {
                    if (o.equals(x.item)) {
                        unlink(x);
                        return true;
                    }
                }
            }
            return false;
        }

判断传进来的是null还是其他，如果不为null,则通过比较传进来的值，如果找到，则通过unlink将该节点删除

2.通过位置索引

public E remove(int index) {
            checkElementIndex(index);
            return unlink(node(index));
        }

index从 0 开始算起，checkElementIndex(index)是判断index是否合法，即大于等于0小于链表的size(注意：是小于size)

3.不传值，在remove中调用removeFirst()

public E remove() {
            return removeFirst();
        }
     public E removeFirst() {
            final Node<E> f = first;
            if (f == null)
                throw new NoSuchElementException();
            return unlinkFirst(f);
        }

## 我们来看一下它是怎么删除节点的 ##

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;
            size--;
            modCount++;
            return element;
        }

首先，将传进来的node节点的值item，节点的前一个节点prev,后一个节点next先保存下来

然后，判断prev是否为空，如果为空，即这个节点是第一个节点，那么我们将要删除的节点的后一个节点，即原来的第二个节点设置为第一，如果prev不为空，即要删除的节点不是第一个节点，则将prev.next指向next

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FiY18xMjM0NTZfX18_size_16_color_FFFFFF_t_70][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FiY18xMjM0NTZfX18_size_16_color_FFFFFF_t_70]: /images/20230528/55e7d5e2e2c24e97be284772fb94a519.png