美文网首页
数据结构之Java List

数据结构之Java List

作者: 郑印 | 来源:发表于2018-11-13 13:31 被阅读26次

本文从线性数据结构顺序表与链表开始分析Java中ArrayList与LinkedList的实现，最后对Java List 接口子类的特点进行一个总结

线性表的顺序存储

线性表的顺序存储结构，指的是用一段地址连续的存储单元依次存储线性表的数据元素。
示意图如下：


摘录来自: 程杰. “大话数据结构。”

在Java中我们使用数组来数据来模拟这样的一种实现，首先我们定义一个List的接口，里面描述了顺序表的基本操作 （后面链表也会用到这个List）


public interface MyList<E> {
    boolean isEmpty();
    void clear();
    int size();
    E get(int i);
    boolean add(E e);
    boolean add(int index , E e);
    E remove(int index);
    int indexOf(E e);
}

以上代码中包含了顺序表的基本操作

  • isEmpty 判断是否为一个空表
  • clear 情况表
  • size 返回表的大小
  • get 获取一个元素
  • add 在表尾部插入一个元素
  • add(index , e) 在指定位置插入一个元素
  • remove 删除指定位置的元素
  • indexOf 范围元素所在的位置

下面我们使用来实现这个接口 , MyArrayList

package com.izhengyin.special.ds.part1;

public class MyArrayList<E>  implements MyList<E>{

    private final static int DEFAULT_CAPACITY = 10;

    private Object[] elements;

    private int size = 0;

    public MyArrayList(){
        this(DEFAULT_CAPACITY);
    }

    public MyArrayList(int capacity){
        elements = new Object[capacity];
    }

    public boolean isEmpty(){
        return size == 0;
    }

    public void clear(){
        if(size <= 0){
            return;
        }
        for(int i = size; i>0; i--){
            elements[i] = null;
        }
        size = 0;
    }

    public int size(){
        return size;
    }

    @SuppressWarnings("unchecked")
    public E get(int i){
       if(size == 0){
            throw new IndexOutOfBoundsException();
       }
       if (i < 0 || i >= size){
           throw new IllegalArgumentException();
       }
       return (E)elements[i];
    }

    public boolean add(E e){
        if(e == null){
            throw new NullPointerException();
        }
        return add(size,e);
    }

    public boolean add(int index , E e){
        if(e == null){
            throw new NullPointerException();
        }
        if(size >= elements.length){
            throw new IndexOutOfBoundsException();
        }
        if(index < 0 || index > size){
            return false;
        }
        if(index < size){
            for(int i = size;i>index;i--){
                elements[i] = elements[i-1];
            }
        }
        elements[index] = e;
        size ++;
        return true;
    }

    @SuppressWarnings("unchecked")
    public E remove(int index){
        if(index<0 || index >= size){
            throw new IllegalArgumentException();
        }
        E oldElem = (E)elements[index];
        for (int i = index;i<size;i++){
            elements[i] = elements[i+1];
        }
        size --;
        elements[size] = null;
        return oldElem;
    }

    public int indexOf(E e){
        if(size <= 0){
            return -1;
        }
        for(int i=0;i<size;i++){
            if(elements[i].equals(e)){
                return i+1;
            }
        }
        return -1;
    }
}

测试

    @Test
    public void myArrayListTest() {
        MyList<String> myList = new MyArrayList<String>(10);
        myList.add("a");
        myList.add("b");
        myList.add("c");
        Assert.assertEquals(myList.size(),3);
        Assert.assertEquals(myList.get(2),"c");
        Assert.assertEquals(myList.remove(1),"b");
        Assert.assertEquals(myList.get(1),"c");
        Assert.assertTrue(myList.add("1"));
        Assert.assertTrue(myList.add("2"));
        Assert.assertFalse(myList.add(8,"3"));
        Assert.assertEquals(myList.size(),4);
        Assert.assertEquals(myList.get(3),"2");
    }

下面我们主要分析一下 get 、add 、remove 三个方法，也就是获取元素，添加元素，删除元素的时间复杂度

  • get(int index) ， 在我们获取某个元素时直接通过数组下标获取,时间复杂度为O(1)
  • add(int index, E e) ， 在我们删除某个元素时，如果元素在末尾时间复杂度为O(1),如果在头部我们需要将数据整体移动一遍，时间复杂度为O(n) ,所以时间复杂度O(n)
  • remove(int index) ， remove与add类似，最好情况为O(1) , 最差为 O(n)

线性表的链式存储

线性表的链式存储有，单链表、循环链表以及双向链表，这里我们直接使用用Java来实现一个简单双向链表,我们还是实现上文中MyList定义的接口

摘录来自: 程杰. “大话数据结构。” 
package com.izhengyin.special.ds.part1;


public class MyLinkedList<E>  implements MyList<E> {

    private Node<E> first;
    private Node<E> last;
    private int size = 0;

    public MyLinkedList(){

    }

    public boolean isEmpty() {
        return size == 0;
    }

    public void clear() {
        Node<E> node = first;
        while (node != null){
            Node<E> nextNode = node.next;
            node.item = null;
            node.next = null;
            node.prev = null;
            node = nextNode;
        }

        first = null;
        last = null;
        size = 0;
    }

    public int size() {
        return size;
    }

    public E getFirst() {
        if(first == null){
            return null;
        }
        return first.item;
    }

    public E getLast() {
        if(last == null){
            return null;
        }
        return last.item;
    }

    /**
     * @param i
     * @return
     */
    public E get(int i) {
        if(size == 0){
            throw new IndexOutOfBoundsException();
        }
        if (i < 0 || i >= size){
            throw new IllegalArgumentException();
        }
        return findNode(i).item;
    }

    /**
     * @param e
     * @return
     */
    public boolean add(E e) {
        if(e == null){
            throw new NullPointerException();
        }
        return add(size,e);
    }

    /**
     * 添加一个节点到 index 的位置
     * 1. size 为0 初始化链表
     * 2. 原本index的位置的节点，作为新节点的下一个节点
     * 3. 原本节点的上一个节点作为新节点的上一个节点
     * 4. 原本节点的上一个节点的下一个节点指向新节点
     * 5. index 为0 头结点指向新节点
     * 6. index 为 size 尾结点指向新节点
     * @param index
     * @param e
     * @return
     */
    public boolean add(int index, E e) {
        if(e == null){
            throw new NullPointerException();
        }
        if(index < 0 || index > size){
            return false;
        }
        //往末尾追加
        if(index == size){
            return addLast(e);
        }


        Node<E> node = findNode(index);
        Node<E> newNode = new Node<E>(node,e,node.prev);
        node.next = newNode;
        node.prev.next = newNode;
        //头结点
        if(index == 0){
            first = newNode;
        }

        size ++;
        return true;
    }

    /**
     *
     * @param index
     * @return
     */
    public E remove(int index) {
        Node<E> node = findNode(index);
        node.prev.next = node.next;
        node.next = node.prev;
        size --;
        return node.item;
    }

    /**
     *
     * @param e
     * @return
     */
    public int indexOf(E e) {
        Node<E> node = first;
        for(int i = 0;i<size;i++){
            if(node.item.equals(e)){
                return i;
            }
            node = node.next;
        }
        return -1;
    }

    private boolean addLast(E e){
        //初始化
        if(size == 0){
            return init(e);
        }
        Node<E> newNode = new Node<E>(first,e,last);
        last.next = newNode;
        first.prev = newNode;
        last = newNode;
        size ++;
        return true;
    }

    /**
     * 初始化空链表
     * @param e
     * @return
     */
    private boolean init(E e){
        Node<E> newNode = new Node<E>(null,e,null);
        newNode.prev = newNode;
        newNode.next = newNode;
        first = newNode;
        last = newNode;
        size ++;
        return true;
    }

    /**
     * 查找节点
     * 如果 index 为0直接返回头结点,否则从1开始循环，直到返回 index 所在的节点
     * @param index
     * @return
     */
    private Node<E> findNode(int index){
        Node<E> node = first;
        if (index == 0) {
            return node;
        }
        for(int i=1;i<=index;i++){
            node = node.next;
        }
        return node;
    }

    private 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;
        }
    }
}

测试

    @Test
    public void MyLinkedListTest() {
        MyList<String> myList = new MyLinkedList<String>();
        myList.add("a");
        myList.add("b");
        myList.add("c");
        Assert.assertEquals(myList.size(),3);
        Assert.assertEquals(myList.get(2),"c");
        Assert.assertEquals(myList.remove(1),"b");
        Assert.assertEquals(myList.get(1),"c");
        Assert.assertTrue(myList.add("1"));
        Assert.assertTrue(myList.add("2"));
        Assert.assertFalse(myList.add(8,"3"));
        Assert.assertEquals(myList.size(),4);
        Assert.assertEquals(myList.get(3),"2");
    }

同样我们主要分析一下 get 、add 、remove 三个方法

  • get(int index) ， 在我们获取某个元素时需要遍历，时间复杂度为O(1)
  • add(int index, E e) , 需要遍历到插入的位置，时间复杂度为O(n)
  • remove(int index) ，需要找到删除元素的位置 ，时间复杂度为O(n)

对比 ArrayList , LinkedList 在数据操作时时间复杂度并没有明显的改善，相比于ArrayList它的优点在于减少的数据搬移成本，缺点在于会占用更多的存储空间,以及随机访问元素性能不高。

Java List 总结

Java 中 实现List接口的集合主要有：ArrayList、LinkedList、Vector、Stack ， 下面我们来逐个总结一下它们的特点

ArrayList

  1. 底层由数组实现，初始大小为10，在空间不够时需要进行数组的copy
  2. 非同步的，线程安全需要使用者自己考虑
  3. 擅长随机访问好，在指定位置添加元素需要进行数据搬移，性能较差

LinkedList

  1. 底层是通过Java引用实现的双向链表，因此相对于ArrayList更占用空间
  2. 非同步的，线程安全需要使用者自己考虑
  3. 写入性能强于ArrayList,随机访问较差

Vector

  • 可以理解为线程安全的ArrayList

Stack

  • Stack继承自Vector，实现一个后进先出的堆栈。Stack提供5个额外的方法使得Vector得以被当作堆栈使用。
  1. push入栈
  2. pop出栈
  3. peek方法得到栈顶的元素
  4. empty方法测试堆栈是否为空
  5. search方法检测一个元素在堆栈中的位置。Stack刚创建后是空栈。

本文是学习极客时间数据结构与算法之美
结合Java语言的一些笔记，如果你对此课程感兴趣可以在下载极客时间App搜索该课程,也可以点击链接查看

相关文章

网友评论

      本文标题：数据结构之Java List

      本文链接：https://www.haomeiwen.com/subject/yxqalftx.html

      延伸阅读

      深度阅读

      • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

      栏目导航

      热点阅读

      关于我们|服务条款|联系我们|数据结构之Java List|投稿指南|网站地图|RSS订阅|排版工具|手机版

      提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

      Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

      备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

      本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

      所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！