持有对象--LinkedList

Leefs 2019-12-04 PM 1641℃ 0条

# 持有对象--LinkedList

### 前言

本小节讲述《Java编程思想》第11.7节，LinkedList.本节中只是作了一个简单介绍，有兴趣的可以在网上多搜一些练习题进行练习一下

### 补充

开篇前小编先对之前的`Arrays.asList`方法作一个简单的补充说明。

Arrays.asList的作用是将数组转化为list,一般是在初始化的时候，设置几个值进去，简化代码，省去add的部分。

**示例**

```java
List<String> ebsCodes = Arrays.asList("USERNAME","REAP","NLS");
```

等同于：

```java
List<String> ebsCodes = new ArrayList();
ebsCodes.add("USERNAME");
ebsCodes.add("REAP");
ebsCodes.add("NLS");
```

也可以使用引用数据类型String类型的数组

```java
String[] s = {"aa","bb","cc"};
List<String> strlist = Arrays.asList(s);
```

**注意：**

> （1）.该方法不适用于基本数据类型(byte,short,int,long,float,double,boolean),但适用于基本数据类型的包装类，如：integer
>
> （2）.该方法将数组与列表连接起来，当更新其中之一时，另一个自动更新
>
> （3）.不支持add和remove方法

### LinkedList介绍

#### 概念

LikedList是List接口的实现类，与ArrayList不同之处是采用的存储结构不同，ArrayList的数据结构为线性表，LinkedList数据结构是链表。

#### **结构特点**

链表是每个元素分配的空间不必连续、插入和删除元素时速度非常快，但访问元素的速度较慢。

LinkedList是一个双向链表，当数据量很大或者操作很频繁的情况下，添加和删除元素时具有比ArrayList更好的性能。但是在元素的查询和修改方面要弱于ArrayList.

#### 结构分析

LinkedList通过first和last引用分别指向链表的第一个和最后一个元素，当链表为空时，first和last都为NULL值。

#### 结构图例

![LinkedList结果分析01.jpg][1]

#### **LinkedList类内部的Node结点代码如下：**

```java
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;
    }
}
```

Node节点一共有三个属性：item代表节点值，prev代表节点的前有一个节点，next代表节点的后一个节点。每个结点都有一个前驱结点和后继结点，并且在 LinkedList中也定义了两个变量分别指向链表中的第一个和最后一个结点。

> transient Node<E> first;
>
> transient Node<E> last;

#### LinkedList方法说明

**1、添加元素到LinkedList**

> + **boolean add(E e)**:在链表尾部添加一个元素，如果成功，返回true，否则返回false。
> + **void addFirst(E e)**:在链表头部插入一个元素。
> + **addLast(E e)**:在链表尾部添加一个元素。
> + **void add(int index, E element)**:在指定位置插入一个元素。

**添加元素到LinkedList示例代码:**

```java
public class LinkedListAddDemo {
    public static void main(String[] args) {
        LinkedList<String> linkedList = new LinkedList<>();

linkedList.add("first");
        linkedList.add("second");
        linkedList.add("third");
        System.out.println(linkedList);

linkedList.addFirst("addFirst");
        System.out.println(linkedList);

linkedList.addLast("addLast");
        System.out.println(linkedList);

linkedList.add(2,"addByIndex");
        System.out.println(linkedList);
    }
}
```

> 运行结果

```java
[first, second, third]
[addFirst, first, second, third]
[addFirst, first, second, third, addLast]
[addFirst, first, addByIndex, second, third, addLast]
```

代码通过add、addFirst、addLast方法加入元素，并通过println输出链表元素

**2、从LinkedList中删除元素**

> + **boolean remove(Object o)**:从当前链表中移除指定的元素。
> + **E remove(int index)**:从当前链表中移除指定位置的元素。
> + **E removeFirst()**:从当前链表中移除第一个元素。
> + **E removeLast()**:从当前链表中移除最后一个元素。
> + **E remove()**:从当前链表中移除第一个元素，同removeLast()相同。

**代码示例**

```java
public class LinkedListRemoveDemo {
    public static void main(String[] args) {
        LinkedList<String> linkedList = new LinkedList<>();
        linkedList.add("first");
        linkedList.add("second");
        linkedList.add("second");
        linkedList.add("third");
        linkedList.add("four");
        linkedList.add("five");
        System.out.println(linkedList);
        linkedList.remove();
        System.out.println("remove:"+linkedList);
        linkedList.remove("second");
        System.out.println("remove(Object):"+linkedList);

linkedList.remove("six");
        System.out.println("remove(Object) not exist:"+linkedList);

linkedList.remove(2);
        System.out.println("remove(index):"+linkedList);

linkedList.removeFirst();
        System.out.println("removeFirst:"+linkedList);

linkedList.removeLast();
        System.out.println("removeLast:"+linkedList);

System.out.println("-------------------------------------");
        linkedList.clear();

linkedList.add("first");
        linkedList.add("second");
        linkedList.add("second");
        linkedList.add("third");
        linkedList.add("four");
        linkedList.add("five");
        System.out.println(linkedList);

linkedList.removeFirstOccurrence("first");
        System.out.println("removeFirstOccurrence:"+linkedList);

linkedList.removeLastOccurrence("first");
        System.out.println("removeLastOccurrence:"+linkedList);
    }
}
```

**运行结果**

```java
[first, second, second, third, four, five]
remove:[second, second, third, four, five]
remove(Object):[second, third, four, five]
remove(Object) not exist:[second, third, four, five]
remove(index):[second, third, five]
removeFirst:[third, five]
removeLast:[third]
-------------------------------------
[first, second, second, third, four, five]
removeFirstOccurrence:[second, second, third, four, five]
removeLastOccurrence:[second, second, third, four, five]
```

代码通过add方法加入元素，再通过remove、removeFirst、removeLast等方法移除元素，并通过println输出操作后的链表元素。

**3、从LinkedList获取元素**

> + **E get(int index)**:从当前链表中获取指定位置的元素。
> + **E getFirst()**:从当前链表中获取第一个元素。
> + **E getLast()**:从当前链表中获取最后一个元素。

**代码示例**

```java
public class LinkedListGetDemo {
    public static void main(String[] args) {
        LinkedList<String> linkedList = new LinkedList<>();

linkedList.get(3);
        System.out.println("get(index):"+linkedList.get(3));

linkedList.getFirst();
        System.out.println("getFirst:"+linkedList.getFirst());

linkedList.getLast();
        System.out.println("getLast:"+linkedList.getLast());

System.out.println(linkedList);
    }
}
```

代码通过add方法加入元素，再通过get、getFirst、getLast方法获取元素，并通过println输出操作后的链表元素。

**4、LinkedList的遍历方法**

同前面介绍的集合类遍历方式一样，LinkedList可以通过迭代器、foreach语句、for循环语句等方法遍历集合的所有元素。

**代码示例**

```java
public class LinkedListTraverseDemo {
    public static void main(String[] args) {
        LinkedList<Integer> llist = new LinkedList<Integer>();
        for(int i=0;i<100000;i++){
            llist.addLast(i);
        }
        //通过一般for循环来遍历LinkedList
        long start = System.currentTimeMillis();
        int size = llist.size();
        for(int i=0;i<size;i++){
            llist.get(i);
        }
        long end = System.currentTimeMillis();
        long total = end - start;
        System.out.println("byCommonFor---------->"+total+"ms");

//通过迭代器来遍历LinkedList
        start = System.currentTimeMillis();
        Iterator iter = llist.iterator();
        while(iter.hasNext()) {
            iter.next();
        }
        end = System.currentTimeMillis();
        total = end - start;
        System.out.println("byIterator-------------->"+total+"ms");

//通过foreach来遍历LinkedList
        start = System.currentTimeMillis();
        for(Integer integ:llist)
            ;
        end = System.currentTimeMillis();
        total = end - start;
        System.out.println("byForEach-------------->"+total+"ms");
    }
}
```

**运行结果**

```java
byCommonFor---------->5463ms
byIterator-------------->3ms
byForEach-------------->1ms
```

代码采用for循环、迭代器、foreach方式，遍历包含10万个元素的LinkedList，通过输出结果可以看出，foreach语句效率最高，其次是迭代器，效率最差的是for循环。

**知识点拨**

LinkedList存储元素的数据结构是双向链表结构，由存储元素的结点连接而成，每一个节点都包含前一个节点的引用，后一个节点的引用和节点存储的值。当一个新节点插入时，只需要修改其中保持先后关系的节点的引用即可。

### **Think In Java中LinkedList介绍**

`LinkedList`也像`ArrayList`一样实现了基本的List接口,但是它执行某些操作(在List的中间插入和移除)时比ArrayList更高效,但在随机访问方面却要逊色一些

LinkedList还添加了可以使其用作栈,队列或双端队列的方法

这些方法有些彼此之间只是名称有差异,或者只是存在些许差异,以使得这些名字在特定用法的上下文环境中更加适用(特别使在Queun中),例如

> 1. 1.getFirst()和element()完全一样,它们都返回列表的头(第一个元素),而不是移除它,如果List为空,则抛出NoSuchElementException. 
>
> 2. 2.peek()方法与这两个方式只是稍有差异,它在列表为空时返回null
> 3. 3.removeFirst()与remove()也是完全一样,它们移除并返回列表的头,而在列表为空时抛出NoSuchElementException. 
> 4. 4.poll()稍有差异,它在列表为空时返回null
> 5. 5.addFirst()与add()和addList()相同,它们都将某个元素插入到列表的尾(端)部.
> 6. 6.removeLast()移除并返回列表的最后一个元素

### 代码示例

```java
public class LinkedListFeatures {
    public static void main(String[] args) {
        LinkedList<Pet> pets = new LinkedList<Pet>(Pets.arrayList(5));

System.out.println(pets);

System.out.println("pets.getFirst(): " + pets.getFirst());

System.out.println("pets.element(): " + pets.element());

System.out.println("pets.peek(): " + pets.peek());

System.out.println("pets.remove(): " + pets.remove());

System.out.println("pets.removeFirst(): " + pets.removeFirst());

System.out.println("pets.poll(): " + pets.poll());

System.out.println(pets);

pets.addFirst(new Rat());
        System.out.println("After addFirst(): " + pets);
        pets.offer(Pets.randomPet());
        System.out.println("After offer(): " + pets);
        pets.add(Pets.randomPet());
        System.out.println("After add(): " + pets);
        pets.addLast(new Hamster());
        System.out.println("After addLast(): " + pets);
        System.out.println("pets.removeLast(): " + pets.removeLast());
    }
}
```

> 运行结果

```java
[Rat, Manx, Cymric, Mutt, Pug]
pets.getFirst(): Rat
pets.element(): Rat
pets.peek(): Rat
pets.remove(): Rat
pets.removeFirst(): Manx
pets.poll(): Cymric
[Mutt, Pug]
After addFirst(): [Rat, Mutt, Pug]
After offer(): [Rat, Mutt, Pug, Cymric]
After add(): [Rat, Mutt, Pug, Cymric, Pug]
After addLast(): [Rat, Mutt, Pug, Cymric, Pug, Hamster]
pets.removeLast(): Hamster
```

*附：[参考文章链接1](https://blog.csdn.net/qq_29534483/article/details/80107224)，[参考文章链接2](http://baijiahao.baidu.com/s?id=1598633392064956200&wfr=spider&for=pc)*

[1]: https://lilinchao.com/usr/uploads/2019/12/392605116.jpg

标签: Java, Java编程思想, JavaSE, 持有对象

非特殊说明，本博所有文章均为博主原创。

如若转载，请注明出处：https://lilinchao.com/archives/252.html

上一篇 JVM学习（十一）--自定义类加载器深入详解

下一篇持有对象--Stack

持有对象--LinkedList

评论已关闭

栏目分类

标签云

友情链接申请

持有对象--LinkedList

评论已关闭

 栏目分类

标签云

友情链接申请

栏目分类

标签云

友情链接申请