欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

集合-LinkedList源码分析(JDK1.8)

程序员文章站 2022-06-07 13:49:30
...

LinkedList是集合框架的一种数据类型.

继承关系:

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, 
    	Deque<E>, (双端队列)
    	    Cloneable, 
    	        java.io.Serializable
{

数据结构:

双向链表实现

特点:

优点: 增加和删除操作很快,不会涉及到数据的移动.
缺点: 访问速度较慢,需要遍历链表.

源码分析:

	/**
	* 链表的长度
	*/
	transient int size = 0;

    /**
	 * 指向链表的第一个节点
     */
    transient Node<E> first;

    /**
     * 指向链表的最后一个节点
     */
    transient Node<E> last;
//Node节点
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;
        }
    }

1.构造方法

//空参构造
public LinkedList() {
}
//可传入一个集合c
public LinkedList(Collection<? extends E> c) {
    this();
    addAll(c);
}

2.添加方法

addAll(Collection c)

public boolean addAll(Collection<? extends E> c) {
        //调用addAll(size,c);// 将一个新集合添加到自己的后面
        // size 是当前集合的大小
        return addAll(size, c);
    }

    //添加新集合到指定下标index
    public boolean addAll(int index, Collection<? extends E> c) {
        //检测index是否合法
        checkPositionIndex(index);

        //将集合转为数组
        Object[] a = c.toArray();
        int numNew = a.length;
        //如果集合长度=0,直接返回false
        if (numNew == 0)
            return false;

        // pred 待插入位置的前驱节点
        // succ index位置的节点
        Node<E> pred, succ;
        //如果index == size,说明是将新集合插入到尾部
        if (index == size) {
            succ = null;
            pred = last;
        } else {
            succ = node(index);
            pred = succ.prev;
        }

        //遍历数组
        for (Object o : a) {
            @SuppressWarnings("unchecked") E e = (E) o;
            Node<E> newNode = new Node<>(pred, e, null);
            //如果待插入的位置是第一个位置
            if (pred == null) {
                //将first指向新节点
                first = newNode;
            } else {
                //设置pre的next指向插入的节点
                pred.next = newNode;
            }
            //pre向后移动
            pred = newNode;
        }

        //最后添加完,succ = null,说明是尾部添加
        if (succ == null) {
            // 在for循环结束时,pre指向的就是最后一个元素,后面没有数据
            // 将last指向pre
            last = pred;
        } else {
            // succ != null ,说明是从中间或者从前面添加数据
            // 将pre的next指向原集合的index位置的数据
            pred.next = succ;
            // 将原集合的index位置 的前驱节点指向pred
            succ.prev = pred;
        }

        //原集合的size + 新插入的数据长度
        size += numNew;
        //修改次数++
        modCount++;
        return true;
    }
//检查index是否合法
private void checkPositionIndex(int index) {
    if (!isPositionIndex(index)) {
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }
}

private boolean isPositionIndex(int index) {
     return index >= 0 && index <= size;
}
  • add(E e)
public boolean add(E e) {
     linkLast(e); 
     return true;
}

  • linkLast(E e)//尾部添加
void linkLast(E e) {
		//获取最后一个节点
        final Node<E> l = last;
        //new一个新节点,将该节点的前驱节点指向 l
        final Node<E> newNode = new Node<>(l, e, null);
        //last指向该新节点
        last = newNode;
        //如果l == null ,则说明是第一次添加,将first指向该节点
        if (l == null) {
            first = newNode;
        } else {
            //将最后一个节点l的next指向新节点
            l.next = newNode;
        }
        //长度++
        size++;
        //修改次数++
        modCount++;
    }
  • add(int index, E e):指定位置添加元素
//往指定位置index添加数据
public void add(int index, E element) {
    //检查index是否合法
    checkPositionIndex(index);
    //如果带插入的位置 == size,说明是尾部添加
    if (index == size) {
        linkLast(element);  //上面介绍过
    } else {
    	//传入待插入元素,并获取index位置元素
        linkBefore(element, node(index));
    }
}
//获取index位置元素
Node<E> node(int index) {
	 //为了提高效率,首先判断index 和size/2的关系
     if (index < (size >> 1)) {
          //小于则从前面进行查找
          Node<E> x = first;
          for (int i = 0; i < index; i++) {
              x = x.next;
          }
          return x;
     } else {
           //大于则从后向前查找
	       Node<E> x = last;
    	   for (int i = size - 1; i > index; i--)
            x = x.prev;
       return x;
     }
}

  • linkBefore(element(待插入元素), node(index)(原链表元素));
void linkBefore(E e, Node<E> succ) {
        //获取原链表index位置节点的前驱节点pred
        final Node<E> pred = succ.prev;
        //创建一个新节点,将新节点的前驱节点指向pred
        final Node<E> newNode = new Node<>(pred, e, succ);
        //将原链表的元素的前驱节点指向新节点
        succ.prev = newNode;
        //如果pred == null ,则说明待插入位置为链表头部
        if (pred == null)
        	//将first指向新节点
            first = newNode;
        else
        	//否则原链表的前驱的后继节点指向新节点
            pred.next = newNode;
        //长度++
        size++;
        //修改次数++
        modCount++;
    }
  • linkFirst(E e) : 头部添加元素(头插法)
//头部添加数据
private void linkFirst(E e) {
		//获取first节点
        final Node<E> f = first;
        //创建新节点,将它的后继节点指向 f
        final Node<E> newNode = new Node<>(null, e, f);
        //更新first节点
        first = newNode;
        //如果f == null, 说明数据为空,将last指向新节点
        if (f == null)
            last = newNode;
        else
        	//否则将f的前驱指向新节点
            f.prev = newNode;
        size++;
        modCount++;
}

3. 删除方法

remove(Object) : 删除指定元素(第一个遇到的)

public boolean remove(Object o) {
	//如果对象==null
    if (o == null) {
        for (Node<E> x = first; x != null; x = x.next) {
             if (x.item == null) {
                  unlink(x);
                  return true;
             }
        }
    } else {
        //对象不为null
        for (Node<E> x = first; x != null; x = x.next) {
             if (o.equals(x.item)) {
                  unlink(x);
                  return true;
             }
        }
    }
    return false;
}
  • unLink(Node x): 将节点从链表中删除
E unlink(Node<E> x) {
    // 获取该节点的数据
    final E element = x.item;
    //获取该节点的next(后继节点)
    final Node<E> next = x.next;    
    //获取该节点的prev(前驱节点)
    final Node<E> prev = x.prev;
    
	//如果前驱节点 == null ,则说明该节点处于链表的头部
    if (prev == null) {
    	//将first指向待删除节点的下一个节点
        first = next;
    } else {
    	//不是头结点,则将当前节点的前驱节点的next指向待删除节点的下一个节点
        prev.next = next;
        //将待删除的节点的前驱置为null
        x.prev = null; //1
    }
    //如果后继节点 == null,则说明该节点处于链表的尾部
    if (next == null) {
    	//将last节点指向待删除节点的前一个节点
        last = prev;
    } else {
    	//不是尾节点,则将当前节点的后继节点的prev指向待删除节点的上一个节点
        next.prev = prev;
        //将待删除节点的next置为null 和 1操作一起 help GC
        x.next = null;
    }
    x.item = null; //将待删除节点数据置为null
    //长度--
    size--;
    //操作次数++
    modCount++;
    //返回删除节点的数据
    return element;
}
  • remove :删除链表的第一个节点
public E remove() {
        return removeFirst();
    }
  • removeFirst(): 删除头结点
public E removeFirst() {
        final Node<E> f = first;
        if (f == null) //如果链表为空,会抛异常
            throw new NoSuchElementException();
        return unlinkFirst(f);
    }
  • unLinkFirst(Node f) : 将头结点从链表中移除
private E unlinkFirst(Node<E> f) {
		//获取头结点的数据
        final E element = f.item;
        //获取头结点的后继节点next
        final Node<E> next = f.next;
        //将头结点的数据置为null
        f.item = null;
        //将头结点的next置为null
        f.next = null; // help GC
        //更新头结点
        first = next;
        //如果next为null,则说明只有一个元素
        if (next == null)
        	//将last指向null
            last = null;
        else
        	//不止一个元素,将f.next的前驱节点指向null
            next.prev = null;
        //长度--
        size--;
        //操作次数++
        modCount++;
        //返回删除的节点的 元素
        return element;
    }

unlinkLast(Node l)

private E unlinkLast(Node<E> l) {
        // 获取最后一个节点的元素
        final E element = l.item;
        //获取最后一个节点的前驱节点prev
        final Node<E> prev = l.prev;
        //将数据置为null
        l.item = null;
        //将最后的节点的前驱指向null
        l.prev = null; // help GC
        //更新last节点
        last = prev;
        //如果前驱节点 == null,则说明只有一个元素,
        if (prev == null)
        	//将first置为null
            first = null;
        else
        	//将前驱节点的next置为null
            prev.next = null;
        //长度--
        size--;
        //修改次数++
        modCount++;
        //返回删除的节点的元素
        return element;
    }

4.获取元素

get(int index):

public E get(int index) {
        checkElementIndex(index);
        return node(index).item;
    }
    
//获取index位置元素
Node<E> node(int index) {
	 //为了提高效率,首先判断index 和size/2的关系
     if (index < (size >> 1)) {
          //小于则从前面进行查找
          Node<E> x = first;
          for (int i = 0; i < index; i++) {
              x = x.next;
          }
          return x;
     } else {
           //大于则从后向前查找
	       Node<E> x = last;
    	   for (int i = size - 1; i > index; i--)
            x = x.prev;
       return x;
     }
}

5. 覆盖方法

public E set(int index, E element) {
		//检验index的合法性
        checkElementIndex(index);
        //获取index位置节点
        Node<E> x = node(index);
        //获取元素
        E oldVal = x.item;
        //更新元素
        x.item = element;
        //返回原来的数据
        return oldVal;
    }

自定义LinkedList

import java.util.NoSuchElementException;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: ZHANFEI
 * Date: 20-8-6
 * Time: 下午4:29
 */
class MyLinkedList<E> {

    //链表长度
    private int size = 0;
    //链表头部
    private Node<E> first;
    //链表尾部
    private Node<E> last;

     private class Node<E> {
        E val;
        Node<E> prev;
        Node<E> next;

        public Node(Node<E> prev,E val,Node<E> next) {
            this.prev = prev;
            this.val = val;
            this.next = next;
        }
    }

    //检测index是否合法
    private boolean checkIndex(int index) {
        if(index < 0 || index > size) {
            throw new IllegalArgumentException("Illegal index " + index);
        }
        return true;
    }

    //获取index位置的节点
    private Node<E> indexOf(int index) {
        if(index < (size >> 1)) {
            Node cur = first;
            //从前往后找
            for(int i=0;i<index;i++) {
                cur = cur.next;
            }
            return cur;
        } else {
            Node cur = last;
            //从后往前走
            for(int i = size -1; i > index; i--) {
                cur = cur.prev;
            }
            return cur;
        }
    }

    //往指定位置添加
    public void add(int index,E e) {
        checkIndex(index);
        if(index == size) {
            addLast(e);
        } else {
            //获取index位置的节点
            Node<E> indexNode = indexOf(index);
            //获取节点的前驱节点和后继节点
            Node<E> prev = indexNode.prev;

            //创建新节点
            Node<E> newNode = new Node<>(prev, e, indexNode);
            //若插入位置为头插
            if(prev == null) {
                first = newNode;
            } else {
                prev.next = newNode;
            }
            size++;
        }
    }

    //添加
    public boolean add(E e) {
        addLast(e);
        return true;
    }

    //头部添加
    public void addFirst(E e) {
        Node node = new Node(null,e,first);
        //第一个节点为null,链表为空
        if(first == null) {
            //将last指向node
            last = node;
        } else {
            //
            first.prev = node;
        }
        //更新first节点
        first = node;
        //长度++
        size++;
    }

    //尾部添加
    public void addLast(E e) {
        Node node = new Node(last, e, null);
        //最后一个节点为null ,则链表为空
        if(last == null) {
            //将first指向node
            first = node;
        } else {
            //链表不为空,last.next指向新节点
            last.next = node;
        }
        //更新last节点
        last = node;
        size++;
    }

    //删除第一个
    public E removeFirst() {
        if(first == null) {
            throw new NoSuchElementException();
        }
        Node<E> cur = first;
        //获取旧值
        E oldVal = cur.val;
        Node next = cur.next;
        //==null 则说明只有一个值
        if(next == null) {
            last = null;
        } else {
            next.prev = null;
        }
        first = next;

        cur.next = null;
        cur.val = null; //help GC

        size--;
        return oldVal;
    }

    //删除尾节点
    public E removeLast() {
        Node<E> cur = last;

        E oldVal = cur.val;
        Node<E> prev = cur.prev;

        //== null 则说明只有一个值
        if(prev == null) {
            first = null;
        } else {
            prev.next = null;
        }
        //更新last
        last = prev;

        cur.prev = null;
        cur.val = null; //help GC

        size--;
        return oldVal;
    }

    //删除
    public E remove(int index) {
        //获取index位置的节点
        Node<E> del = indexOf(index);
        E oldVal = unlink(del);
        return oldVal;
    }

    public E unlink(Node<E> del) {
        //获取数据
        E oldVal = del.val;
        //获取待删除节点的前驱和后继
        Node<E> prev = del.prev;
        Node<E> next = del.next;

        //若prev == null ,说明该节点是第一个节点
        if(prev == null) {
            first = next;
        } else {
            //将前一个节点的next指向它后一个节点(越过它)
            prev.next = next;
            //将该节点的next指向null
            del.prev = null;
        }

        //说明该节点是最后一个节点
        if(next == null) {
            last = prev;
        } else {
            next.prev = prev;
            del.next = null;
        }

        del.val = null; //help GC
        //长度--
        size--;
        return oldVal;
    }

    //删除指定元素
    public boolean removeObj(E e) {
        if(e == null) {
            for (Node cur = first;cur!=null;cur = cur.next) {
                if(cur.val == null) {
                    unlink(cur);
                    return true;
                }
            }
        } else {
            for (Node cur = first;cur!=null;cur = cur.next) {
                if(e.equals(cur.val)) {
                    unlink(cur);
                    return true;
                }
            }
        }
        return false;
    }

    //获取
    public E get(int index) {
        return indexOf(index).val;
    }

    //覆盖
    public E set(int index,E e) {
        //获取index位置的节点
        Node<E> eNode = indexOf(index);
        //获取值
        E oldVal = eNode.val;
        //设置为新值
        eNode.val = e;
        //返回旧值
        return oldVal;
    }

    //contains包含
    public boolean contains(E e) {
        Node cur = first;
        for (int i = 0; i < size; i++) {
            if(e.equals(cur.val)) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

    //toString
    public String toString(){
        StringBuilder sb = new StringBuilder();
        sb.append("[");
        Node cur = first;
        while (cur != last) {
            sb.append(cur.val+", ");
            cur = cur.next;
        }
        sb.append(last.val);
        sb.append("]");
        return sb.toString();
    }

}

public class LinkedListTest {

    public static void main(String[] args) {
        MyLinkedList<String> list = new MyLinkedList<>();
        list.add("1");
        list.add("2");
        list.addFirst("0");
        list.addFirst("1");
        list.add("3");
        list.add("4");
        list.addFirst("2");
        list.addFirst("3");

        System.out.println("添加元素之后: "+list);
        list.remove(2);
        list.removeObj("1");
        System.out.println("删除: "+list);

        list.removeFirst();
        list.removeLast();
        System.out.println("删除头和尾"+list);

        System.out.println("是否包含: "+list.contains("1"));

        System.out.println("获取index=1: "+list.get(1));

        System.out.println("更新0号位置的值: "+list.set(0, "s"));
        
    }
}
相关标签: 集合