linkedlist类的特点,LinkedList类特点介绍?

KLQ 2020-08-25 10:51:44 java常见问答 6131

对于linkedlist你了解多少呢?下面要给大家介绍的就是linkedlist类的特点方面的内容,一起来对linkedlist进行一下了解吧。

linkedlist具有以下的几个特点:

1、null值:它可以有多个null值

2、数据重复性:数据是可以重复的

3、数据有序性:保证了插入数据的有序性

底层数据结构

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底层提供的是双向链表

继承关系

public class LinkedList < E > extends AbstractSequentialList < E > implements List < E > , Deque < E > , Cloneable, java.io.Serializable
{}

linkedlist继承了AbstractSequentialList类,它继承了AbstractList类。

linkedlist实现了List接口,Deque接口。

能够克隆,能够进行反序列化以及序列化操作。

基本属性

transient int size = 0; //表示当前集合存储数据个数
transient Node < E > first; //第一个节点
transient Node < E > last; //最后一个节点
private static final long serialVersionUID = 876323262645176354 L; //用于Java的序列化机制
protected transient int modCount = 0; //表示的是版本控制,添加,删除,修改之类的操作都会进行++操作

构造函数

//无参构造函数,构造出一个空列表
public LinkedList()
{}
//使用集合的构造方法,先构造出一个空列表,之后,再将集合当中所有元素添加到列表里面
public LinkedList(Collection < ? extends E > c)
{
    this();
    addAll(c);
}

主要的实现方式

//头插法插入指定结点
private void linkFirst(E e)
{
    final Node < E > f = first;
    final Node < E > newNode = new Node < > (null, e, f);
    first = newNode;
    if (f == null)
        last = newNode;
    else
        f.prev = newNode;
    size++;
    modCount++;
}
//尾插法插入指定结点
void linkLast(E e)
{
    final Node < E > l = last;
    final Node < E > newNode = new Node < > (l, e, null);
    last = newNode;
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    size++;
    modCount++;
}
//将指定结点插入到指定节点之前
void linkBefore(E e, Node < E > succ)
{
    final Node < E > pred = succ.prev;
    final Node < E > newNode = new Node < > (pred, e, succ);
    succ.prev = newNode;
    if (pred == null)
        first = newNode;
    else
        pred.next = newNode;
    size++;
    modCount++;
}
//头删法删除结点
private E unlinkFirst(Node < E > f)
{
    final E element = f.item;
    final Node < E > next = f.next;
    f.item = null;
    f.next = null;
    first = next;
    if (next == null)
        last = null;
    else
        next.prev = null;
    size--;
    modCount++;
    return element;
}
//尾删法删除结点
private E unlinkLast(Node < E > l)
{
    final E element = l.item;
    final Node < E > prev = l.prev;
    l.item = null;
    l.prev = null;
    last = prev;
    if (prev == null)
        first = null;
    else
        prev.next = null;
    size--;
    modCount++;
    return element;
}
//删除指定结点
E unlink(Node < E > x)
{
    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;
}
//返回此列表的第一个元素
public E getFirst()
{
    final Node < E > f = first;
    if (f == null)
        throw new NoSuchElementException();
    return f.item;
}
//返回此列表的最后一个元素
public E getLast()
{
    final Node < E > l = last;
    if (l == null)
        throw new NoSuchElementException();
    return l.item;
}
//头删法删除结点
public E remove()
{
    return removeFirst();
}
//移除此列表中指定位置处的元素
public E remove(int index)
{
    checkElementIndex(index);
    return unlink(node(index));
}
//移除并返回此列表的第一个元素
public E removeFirst()
{
    final Node < E > f = first;
    if (f == null)
        throw new NoSuchElementException();
    return unlinkFirst(f);
}
//移除并返回此列表的最后一个元素
public E removeLast()
{
    final Node < E > l = last;
    if (l == null)
        throw new NoSuchElementException();
    return unlinkLast(l);
}
//删除指定元素
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;
}
//从此列表中移除所有元素
public void clear()
{
    for (Node < E > x = first; x != null;)
    {
        Node < E > next = x.next;
        x.item = null;
        x.next = null;
        x.prev = null;
        x = next;
    }
    first = last = null;
    size = 0;
    modCount++;
}
//将给定元素插入此列表的开头
public void addFirst(E e)
{
    linkFirst(e);
}
//将给定元素追加到此列表的结尾
public void addLast(E e)
{
    linkLast(e);
}
//判断此列表是否包含指定元素
public boolean contains(Object o)
{
    return indexOf(o) != -1;
}
//返回此列表的元素数				
public int size()
{
    return size;
}
//尾插法插入指定结点				
public boolean add(E e)
{
    linkLast(e);
    return true;
}
//返回此列表中指定位置处的元素
public E get(int index)
{
    checkElementIndex(index);
    return node(index)
        .item;
}
//将此列表中指定位置的元素替换为指定的元素
public E set(int index, E element)
{
    checkElementIndex(index);
    Node < E > x = node(index);
    E oldVal = x.item;
    x.item = element;
    return oldVal;
}
//将指定集合中所有元素添加到指定集合的后面
public boolean addAll(Collection < ? extends E > c)
{
    return addAll(size, c);
}
//在指定位置插入指定集合
public boolean addAll(int index, Collection < ? extends E > c)
{
    checkPositionIndex(index);
    Object[] a = c.toArray();
    int numNew = a.length;
    if (numNew == 0)
        return false;
    Node < E > pred, succ;
    if (index == size)
    {
        succ = null;
        pred = last;
    }
    else
    {
        succ = node(index);
        pred = succ.prev;
    }
    for (Object o: a)
    {
        Node < E > newNode = new Node < > (pred, e, null);
        if (pred == null)
            first = newNode;
        else
            pred.next = newNode;
        pred = newNode;
    }
    if (succ == null)
    {
        last = pred;
    }
    else
    {
        pred.next = succ;
        succ.prev = pred;
    }
    size += numNew;
    modCount++;
    return true;
}
//将指定元素插入到指定下标位置之前
public void add(int index, E element)
{
    checkPositionIndex(index);
    if (index == size)
        linkLast(element);
    else
        linkBefore(element, node(index));
}
//判断下标是否合法
private boolean isElementIndex(int index)
{
    return index >= 0 && index < size;
}
private boolean isPositionIndex(int index)
{
    return index >= 0 && index <= size;
}
private void checkElementIndex(int index)
{
    if (!isElementIndex(index))
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
private void checkPositionIndex(int index)
{
    if (!isPositionIndex(index))
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
//返回指定位置的结点
Node < E > node(int index)
{
    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;
    }
}
//返回指定元素第一次出现的下标
public int indexOf(Object o)
{
    int index = 0;
    if (o == null)
    {
        for (Node < E > x = first; x != null; x = x.next)
        {
            if (x.item == null)
                return index;
            index++;
        }
    }
    else
    {
        for (Node < E > x = first; x != null; x = x.next)
        {
            if (o.equals(x.item))
                return index;
            index++;
        }
    }
    return -1;
}
//返回指定元素最后一次出现的下标
public int lastIndexOf(Object o)
{
    int index = size;
    if (o == null)
    {
        for (Node < E > x = last; x != null; x = x.prev)
        {
            index--;
            if (x.item == null)
                return index;
        }
    }
    else
    {
        for (Node < E > x = last; x != null; x = x.prev)
        {
            index--;
            if (o.equals(x.item))
                return index;
        }
    }
    return -1;
}
public E peek()
{
    final Node < E > f = first;
    return (f == null) ? null : f.item;
}
public E element()
{
    return getFirst();
}
public E poll()
{
    final Node < E > f = first;
    return (f == null) ? null : unlinkFirst(f);
}
public boolean offer(E e)
{
    return add(e);
}
public boolean offerFirst(E e)
{
    addFirst(e);
    return true;
}
public boolean offerLast(E e)
{
    addLast(e);
    return true;
}
public E peekFirst()
{
    final Node < E > f = first;
    return (f == null) ? null : f.item;
}
public E peekLast()
{
    final Node < E > l = last;
    return (l == null) ? null : l.item;
}
public E pollFirst()
{
    final Node < E > f = first;
    return (f == null) ? null : unlinkFirst(f);
}
public E pollLast()
{
    final Node < E > l = last;
    return (l == null) ? null : unlinkLast(l);
}
public void push(E e)
{
    addFirst(e);
}
public E pop()
{
    return removeFirst();
}
//返回ListIterator迭代器
public ListIterator < E > listIterator(int index)
{
    checkPositionIndex(index);
    return new ListItr(index);
}
//返回Iterator迭代器			  
public Iterator < E > descendingIterator()
{
    return new DescendingIterator();
}
//返回此 LinkedList 的浅表复制			  
public Object clone()
{
    LinkedList < E > clone = superClone();
    clone.first = clone.last = null;
    clone.size = 0;
    clone.modCount = 0;
    for (Node < E > x = first; x != null; x = x.next)
        clone.add(x.item);
    return clone;
}
//以正确顺序返回包含此列表中所有元素的数组			   
public Object[] toArray()
{
    Object[] result = new Object[size];
    int i = 0;
    for (Node < E > x = first; x != null; x = x.next)
        result[i++] = x.item;
    return result;
}
//以正确顺序返回包含此列表中所有元素的数组,返回数组的运行时类型即为指定数组的类型
public < T > T[] toArray(T[] a)
{
    if (a.length < size)
        a = (T[]) java.lang.reflect.Array.newInstance(a.getClass()
            .getComponentType(), size);
    int i = 0;
    Object[] result = a;
    for (Node < E > x = first; x != null; x = x.next)
        result[i++] = x.item;
    if (a.length > size)
        a[size] = null;
    return a;
}
//通过JAVA对象流进行序列化和反序列化
private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException
{
    s.defaultWriteObject();
    s.writeInt(size);
    for (Node < E > x = first; x != null; x = x.next)
        s.writeObject(x.item);
}
private void readObject(java.io.ObjectInputStream s) throws java.io.IOException, ClassNotFoundException
{
    s.defaultReadObject();
    int size = s.readInt();
    for (int i = 0; i < size; i++)
        linkLast((E) s.readObject());
}

效率

增加和删除的效率比较高,查询和修改的效率比较的低。

那么关于linkedlist类的特点就简单的给大家介绍到这里了,假如你还想了解更多关于这方面的内容,请继续关注奇Q工具网的java入门栏目了解吧。

推荐阅读:

inkedlist特点是什么?linkedlist用法介绍

Linkedlist是每次遍历都从第一个吗?有多少种遍历方式?

arraylist和linklist区别分别有哪些?