什么是线性表:

线性表是具有相同特性的数据元素的一个有限序列

  • 所有数据元素类型相同
  • 线性表是有限个数据元素构成的
  • 线性表中数据元素与位置相关,即每个数据元素有唯一的序号

线性表的逻辑表示:

(a 0 ,a 1 , ... ,a i ,a i+1 ,... ,a n-1)

用图形表示的逻辑结构:

image-20220317175308811.png

线性表的顺序存储结构——顺序表:

代码实现:

  • List():创建线性表
  • boolean add(E e):将指定元素追加到此列表的末尾(可选操作)
  • void add(int index, E element):指定的元素插入此列表中的指定位置(可选操作)
  • void clear():从此列表中删除所有元素(可选操作)
  • boolean contains(Object o):如果此列表包含指定的元素,则返回true
  • E get(int index):返回此列表中指定位置的元素
  • int indexOf(Object o):返回此列表中指定元素的第一次出现的索引,如果此列表不包含元素,则返回-1
  • boolean isEmpty():如果此列表中不包含元素,则返回true
  • E remove(int index):删除该列表中指定位置的元素(可选操作)
  • boolean remove(Object o):从列表中删除指定元素的第一个出现(如果存在)(可选操作)
  • E set(int index, E element):用指定的元素(可选操作)替换此列表中指定位置的元素
  • int size():返回此列表中的元素数
  • String toString():将线性表转换为字符串

MyArrayList实现:

package blogArrayList;

import java.util.Collection;
import java.util.Iterator;
import java.util.List;
import java.util.ListIterator;

public class MyArrayList<E> implements List {

    private static final Object[] EMPTY_ELEMENTDATA = {};
    Object[] elementDate;//存放元素的数组
    private int size;//定义长度
    transient Object[] elementData;

    public MyArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
            elementDate = new Object[initialCapacity];
        }else {
            elementDate = EMPTY_ELEMENTDATA;
        }
        this.size = 0;
    }

    public MyArrayList() {
//        初始化MyArrayList的长度为10
        elementDate = new Object[10];
        this.size = 0;
    }

    public MyArrayList(Collection<? extends E> c) {
        elementDate = new Object[c.size()];
        int index = 0;
        for (Object object : c) {
            this.elementDate[index++] = object;
        }
        this.size = c.size();

    }

    @Override
    public int size() {
//        返回此列表中的元素数
        return this.size;
    }

    public void trimToSize() {
//        修改这个ArrayList 实例的容量大小是当前列表的当前大小
        Object[] temp = new Object[this.size];
        for (int i = 0; i < this.size; i ++) {
            temp[i] = this.elementDate[i];
        }
        elementDate = temp;
    }

    @Override
    public boolean isEmpty() {
//        如果此列表不包含元素,则返回true
        return this.size == 0;
    }

    @Override
    public boolean contains(Object o) {
//        如果此列表包含指定的元素,则返回true
        return this.indexOf(o) != -1;
    }

    @Override
    public Iterator iterator() {
//        以正确的顺序返回该列表中的元素的迭代器
        return this.listIterator();
    }

    @Override
    public Object[] toArray() {
        return new Object[0];
    }

    public void ensureCapacity(int minCapacity) {
        //如果需要,增加此ArrayList实例的容量,以确保它至少可以容纳最小容量参数指定的元素数
        if (minCapacity > this.elementDate.length) {
            Object[] temp = new Object[minCapacity];
            for (int i = 0; i < this.size; i ++) {
                temp[i] = this.elementDate[i];
            }
            this.elementDate = temp;
        }
    }
    @Override
    public boolean add(Object e) {
//        将指定的元素追加到此列表的末尾
//        数组元素个数达到存储能力最大值,怎么办?
        if (this.size == this.elementDate.length) {
            //扩容
            this.ensureCapacity(this.elementDate.length + this.elementDate.length / 2);
        }
        this.elementDate[size] = e;
        this.size ++;
        return true;
    }

    @Override
    public boolean remove(Object o) {
//        从列表中删除指定元素的第一个出现(如果存在)
        int index = this.indexOf(o);
        if (index == -1) {
            return false;
        }else {
            this.remove(index);
            return true;
        }
    }

    @Override
    public boolean addAll(Collection c) {
//        按指定集合的Iterator返回顺序将指定集合中的所有元素追加到此列表的末尾
        this.addAll(this.size,c);
        return true;
    }

    @Override
    public boolean addAll(int index, Collection c) {
//        将指定集合中的所有元素插入到此列表中,从指定的位置开始
        if (index < 0 || index > size()) {
            throw new IndexOutOfBoundsException();
        }
        if (this.size + c.size() > this.elementDate.length) {
            this.ensureCapacity(this.elementDate.length + this.elementDate.length / 2 + c.size());
        }
        for (int i = size + c.size() - 1; i >= index + c.size(); i --) {
            this.elementDate[i] = this.elementDate[i - c.size()];
        }
        for(Object object : c) {
            this.elementDate[index ++] = object;
        }
        this.size = this.size + c.size();
        return true;
    }

    @Override
    public void clear() {
//        从列表中删除所有元素
        this.size = 0;
    }

    @Override
    public Object get(int index) {
//        返回此列表中指定位置的元素
        if (index < 0 || index >= size()) {
            throw new IndexOutOfBoundsException();
        }
        return this.elementDate[index];
    }

    @Override
    public Object set(int index, Object element) {
//        用指定的元素替换此列表中指定位置的元素
        if (index < 0 || index >= size()) {
            throw new IndexOutOfBoundsException();
        }
        Object old = this.elementDate[index];
        this.elementDate[index] = element;
        return old;
    }

    @Override
    public void add(int index, Object element) {
//        在此列表中的指定位置插入指定的元素
        if (index < 0 || index > size()) {
            throw new IndexOutOfBoundsException();
        }
        if (this.size == this.elementDate.length) {//扩容
            this.ensureCapacity(this.elementDate.length + this.elementDate.length / 2);
        }
        for (int i = this.size - 1; i >= index; i --) {
            this.elementDate[i + 1] = this.elementDate[i];
        }
        this.elementDate[index] = element;
        this.size ++;
    }

    @Override
    public Object remove(int index) {
//        删除该列表中指定位置的元素
        if (index < 0 || index > size()) {
            throw new IndexOutOfBoundsException();
        }
        Object o = this.elementDate[index];
        for (int i = index; i < size - 1; i ++) {
            this.elementDate[i] = this.elementDate[i + 1];
        }
        this.size --;
        return o;
    }

    @Override
    public int indexOf(Object o) {
//        返回此列表中指定元素的第一次出现的索引,如果此列表不包含元素,则返回-1
        if (o == null) {
            for (int i = 0; i < this.size; i ++) {
                if (this.elementDate[i] == null)
                    return i;
            }
        }else {
            for (int i = 0; i < this.size; i ++) {
                if (this.elementDate[i].equals(o))
                    return i;
            }
        }
        return -1;
    }

    @Override
    public int lastIndexOf(Object o) {
        // 返回此列表中指定元素的最后一次出现的索引,如果此列表不包含元素,则返回-1。
        return lastIndexOfRange(o, 0, size);
    }

    int lastIndexOfRange(Object o, int start, int end) {
        Object[] es = elementData;
        if (o == null) {
            for (int i = end - 1; i >= start; i--) {
                if (es[i] == null) {
                    return i;
                }
            }
        } else {
            for (int i = end - 1; i >= start; i--) {
                if (o.equals(es[i])) {
                    return i;
                }
            }
        }
        return -1;
    }

    @Override
    public ListIterator listIterator() {
//        返回列表中的列表迭代器(按适当的顺序)
        return this.listIterator(0);
    }

    @Override
    public ListIterator listIterator(int index) {
//从列表中的指定位置开始,返回列表中的元素(按正确顺序)的列表迭代器
        if (index < 0 || index >= size()) {
            throw new IndexOutOfBoundsException();
        }
        return new ListIterator<E>() {
            int flag = index;
            @Override
            public boolean hasNext() {
                return flag < size;
            }

            @Override
            public E next() {
                flag ++;
                return (E) elementDate[flag - 1];
            }

            @Override
            public boolean hasPrevious() {
                return false;
            }

            @Override
            public E previous() {
                return null;
            }

            @Override
            public int nextIndex() {
                return 0;
            }

            @Override
            public int previousIndex() {
                return 0;
            }

            @Override
            public void remove() {

            }

            @Override
            public void set(Object o) {

            }

            @Override
            public void add(Object o) {

            }
        };
    }

    @Override
    public List subList(int fromIndex, int toIndex) {
//        返回此列表中指定的 fromIndex (包括)和 toIndex之间的独占视图
        if (fromIndex < 0 || toIndex > size) {
            throw new IndexOutOfBoundsException();
        }
        if (fromIndex > toIndex) {
            throw new IllegalArgumentException();
        }
        MyArrayList<E> sub = new MyArrayList<>();

        for (int i = fromIndex; i < toIndex; i ++) {
            sub.elementDate[i - fromIndex] = this.elementDate[i];
        }
        sub.size = toIndex - fromIndex;
        return sub;
    }

    @Override
    public boolean retainAll(Collection c) {
//        仅保留此列表中包含在指定集合中的元素
        int i = 0;
        int j = 0;
        while (j < this.size) {
            if (c.contains(this.elementDate[j])) {
                this.elementDate[i] = this.elementDate[j];
                i ++;
            }
            j ++;
        }
        this.size = i;
        return true;
    }

    @Override
    public boolean removeAll(Collection c) {
//        从此列表中删除指定集合中包含的所有元素
        int i = 0;
        int j = 0;
        while (j < this.size) {
            if (!c.contains(this.elementDate[j])) {
                this.elementDate[i] = this.elementDate[j];
                i ++;
            }
            j ++;
        }
        this.size = i;
        return true;
    }

    @Override
    public boolean containsAll(Collection c) {
//        如果此列表包含指定 集合的所有元素,则返回true
        for (Object object : c) {
            if (!this.contains(object)) {//只要发现列表中没有当前元素,立即返回false
                return false;
            }
        }
        return true;
    }

    @Override
    public Object[] toArray(Object[] a) {
        return new Object[0];
    }

    @Override
    public String toString() {
//        返回当前List的字符串表示
        String str = "[";
        for (int i = 0; i < size-1; i ++) {
            str += this.elementDate[i] + ",";
        }
        if (size > 0) {
            str += this.elementDate[size-1];
        }
        str += "]";
        return str;
    }
}

线性表的链式存储结构——链表:

结点包含有元素值和前后继结点的地址信息

  • 如果每个结点只设置一个指向其后继结点的指针成员,这样的链表称为线性单向链接表,简称单链表

image-20220509195850979.png

  • 如果每个结点中设置两个指针成员,分别用以指向其前驱结点和后继结点,这样的链表称之为双向链接表,简称双链表

image-20220509200119246.png

单链表的实现(带头节点):

每个结点为Node<E>泛型类对象,包括存储元素的数据成员data(设其数据类型为E)和存储后继结点的指针成员next

class Node<E>
{
    E item;
    Node(E element,Node<E> next) {
        this.item = element;
        this.next = next;
    }
}

单链表泛型类MyLinkedList<E>

public class MyLinkedList<E>//单链表泛型类
{
    Node<E> head;//存放头节点
    public MyLinkedList()//构造方法
    {
        head = new Node<E>(null,null)//创建头结点
    }
}

MyLinkedList实现:

import java.util.Collection;
import java.util.Iterator;
import java.util.List;
import java.util.ListIterator;

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

    Node<E> head;

    private static class Node<E> {
        E item;
        Node<E> next;

        Node(E element, Node<E> next) {
            this.item = element;
            this.next = next;
        }
    }

    public MyLinkedList() {
//        构造一个空链表
        head = new Node<>(null,null);
    }

    public MyLinkedList(Collection<? extends E> c) {
//        构造一个包含指定集合的元素的列表,按照它们由集合的迭代器返回的顺序
        this();
        Node<E> p = head;

        for(E e : c) {
            Node<E> tNode = new Node<>(e,null);
            p.next = tNode;
            p = p.next;
        }

    }

    @Override
    public int size() {
//        返回此列表中的元素数
        int count = 0;
        Node<E> pNode = head.next;
        while (pNode != null) {
            count ++;
            pNode = pNode.next;
        }
        return count;
    }

    @Override
    public boolean isEmpty() {
        return false;
    }

    @Override
    public boolean contains(Object o) {
        return false;
    }

    @Override
    public Iterator<E> iterator() {
//        以正确的顺序返回该列表中元素的迭代器
        return new Iterator<E>() {
            Node<E> pNode = head;
            @Override
            public boolean hasNext() {
                return pNode.next != null;
            }

            @Override
            public E next() {
                E o = pNode.next.item;
                pNode = pNode.next;
                return o;
            }
        };
    }

    @Override
    public Object[] toArray() {
        return new Object[0];
    }

    @Override
    public <T> T[] toArray(T[] ts) {
        return null;
    }

    @Override
    public boolean add(E e) {
//        将指定的元素追加到此列表的末尾(可选操作)
        Node<E> pNode = head;
        while (pNode.next != null) {//pNode最终指向最后一个节点
            pNode = pNode.next;
        }
        Node<E> tNode = new Node<>(e,null);
        pNode.next = tNode;
        return true;
    }

    @Override
    public boolean remove(Object o) {
//        从列表中删除指定元素的第一次出现(如果存在)(可选操作)
        Node<E> pNode = head;
        while (pNode.next != null && !pNode.next.item.equals(o)) {
            pNode = pNode.next;
        }
        if (pNode.next == null) {
            if (pNode.item.equals(o)) {
                pNode.next = pNode.next.next;
                return true;
            }else {
                return false;
            }
        }else {
            pNode.next = pNode.next.next;
            return true;
        }
    }

    @Override
    public boolean containsAll(Collection<?> collection) {
        return false;
    }

    @Override
    public boolean addAll(Collection<? extends E> collection) {
        return false;
    }

    @Override
    public boolean addAll(int i, Collection<? extends E> collection) {
        return false;
    }

    @Override
    public boolean removeAll(Collection<?> collection) {
        return false;
    }

    @Override
    public boolean retainAll(Collection<?> collection) {
        return false;
    }

    @Override
    public void clear() {
//        从列表中删除所有元素(可选操作)
        head.next = null;
    }

    @Override
    public E get(int index) {
//        返回此列表中指定位置的元素
        if (index < 0) {
            throw new IndexOutOfBoundsException();
        }
        Node<E> pNode = head.next;
        int i = 0;
        while (pNode != null && i < index) {
            pNode = pNode.next;
            i ++;
        }
        if (pNode == null) {
            throw new IndexOutOfBoundsException();
        }
        return pNode.item;
    }

    @Override
    public E set(int index, E element) {
//        用指定的元素(可选操作)替换此列表中指定位置的元素
        if (index < 0) {
            throw new IndexOutOfBoundsException();
        }
        Node<E> pNode = head.next;
        int i = 0;
        while (pNode != null && i < index) {
            pNode = pNode.next;
            i ++;
        }
        if (pNode == null) {
            throw new IndexOutOfBoundsException();
        }

        E tempE = pNode.item;
        pNode.item = element;
        return tempE;
    }

    @Override
    public void add(int index, E element) {
//        将指定的元素插入到此列表中的指定位置(可选操作)
        if (index < 0) {
            throw new IndexOutOfBoundsException();
        }
        int i = 0;
        Node<E> pNode = head;
        while (i < index && pNode != null) {
            i ++;
            pNode = pNode.next;
        }
        if (i < index) {
            throw new IndexOutOfBoundsException();
        }
        Node<E> tNode = new Node<E>(element,pNode.next);
        pNode.next = tNode;
    }

    @Override
    public E remove(int i) {
        return null;
    }

    @Override
    public int indexOf(Object o) {
        return 0;
    }

    @Override
    public int lastIndexOf(Object o) {
        return 0;
    }

    @Override
    public ListIterator<E> listIterator() {
        return null;
    }

    @Override
    public ListIterator<E> listIterator(int i) {
        return null;
    }

    @Override
    public List<E> subList(int i, int i1) {
        return null;
    }

    public String toString() {
        String string = "[";
        Node<E> p = head;
        if (p.next != null) {
            while (p.next.next != null) {
                p = p.next;
                string = string + p.item + ", ";
            }
            string = string + p.next.item + "]";
        }else {
            string = string + "]";
        }

        return string;
    }
}

双链表的实现(不带头节点):

image-20220510185715572.png

每个结点为Node<E>泛型类对象,包括存储元素的数据成员item(设其数据类型为E)、存储前驱节点指针成员prev和后继结点的指针成员next

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

MyDLinkedList实现:

import java.util.Collection;
import java.util.Iterator;
import java.util.List;
import java.util.ListIterator;

//MyDLinkedList实现了LIst的大部分功能,模拟实现了不带头节点的非循环双链表
public class MyDLinkedList<E> implements List<E> {
    int size = 0;//元素个数,为size()等方法节约时间
    Node<E> first;//指向第一个结点
    Node<E> last;//指向最后一个结点

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

    public MyDLinkedList() {
//        构造一个空列表
    }

    public MyDLinkedList(Collection<? extends E> c) {
//        构造一个包含指定集合的元素的列表,按照它们由集合的迭代器返回的顺序
    }

//    添加元素e作为列表的第一个元素
    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++;
        }
    }

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

    @Override
    public int size() {
//        返回此列表中的元素数
        return 0;
    }

    @Override
    public boolean isEmpty() {
//        如果此列表不包含元素,则返回true
        return false;
    }

    @Override
    public boolean contains(Object o) {
//        如果此列表包含指定的元素,则返回true
        return false;
    }

    @Override
    public Iterator<E> iterator() {
//        以正确的顺序返回该列表中的元素的迭代器
        return null;
    }

    @Override
    public Object[] toArray() {
//        以正确的顺序(从第一个到最后一个元素)返回一个包含此列表中所有元素的数组
        return new Object[0];
    }

    @Override
    public <T> T[] toArray(T[] ts) {
        return null;
    }

    @Override
    public boolean add(E e) {
//        将指定的元素追加到此列表的末尾(可选操作)
        this.linkLast(e);
        return true;
    }

    @Override
    public boolean remove(Object o) {
//        从列表中删除指定元素的第一个出现(如果存在)(可选操作)
        Node<E> pNode = first;
        while (pNode != null && !pNode.item.equals(o)) {
            pNode = pNode.next;
        }
        if (pNode != null) {
            pNode.next.prev = pNode.prev;
            pNode.prev.next = pNode.next;
            size--;
            return true;
        }else {
            return false;
        }
    }

    @Override
    public boolean containsAll(Collection<?> collection) {
        return false;
    }

    @Override
    public boolean addAll(Collection<? extends E> collection) {
        return false;
    }

    @Override
    public boolean addAll(int i, Collection<? extends E> collection) {
        return false;
    }

    @Override
    public boolean removeAll(Collection<?> collection) {
        return false;
    }

    @Override
    public boolean retainAll(Collection<?> collection) {
        return false;
    }

    @Override
    public void clear() {
//        从此列表中删除所有元素
        first = last = null;
        size = 0;
    }

    @Override
    public E get(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException();
        }
        Node<E> pNode = first;
        int i = 0;
        while (i < index && pNode != null) {
            pNode = pNode.next;
        }
        return pNode.item;
    }

    @Override
    public E set(int i, E e) {
        return null;
    }

    @Override
    public void add(int i, E e) {

    }

    @Override
    public E remove(int i) {
        return null;
    }

    @Override
    public int indexOf(Object o) {
        return 0;
    }

    @Override
    public int lastIndexOf(Object o) {
        return 0;
    }

    @Override
    public ListIterator<E> listIterator() {
        return null;
    }

    @Override
    public ListIterator<E> listIterator(int i) {
        return null;
    }

    @Override
    public List<E> subList(int i, int i1) {
        return null;
    }
}

顺序表和链表的比较:

基于空间的考虑:

存储密度 = 结点中数据本身占用的存储量 / 整个结点占用的存储量

  • 一般地,存储密度越大,存储空间的利用率就越高
  • 一个顺序表的存储密度为1,而链表的存储密度小于1,仅从存储密度看,顺序表的存储空间利用率高
  • 顺序表需要预先分配空间,所以数据占用一整片地址连续的内存空间,如果分配的空间过小,易出现溢出,需要扩展空间导致大量元素移动而降低效率,如果分配空间过大,会导致空间空闲而浪费,而链表的存储空间是动态分配的,只要内存有空闲,就不会出现溢出

结论:当线性表的长度变化不大,易于事先确定的情况下,为了节省存储空间,宜采用顺序表作为存储结构,当线性表的长度变化交大,难以估计其存储空间,宜采用链表作为其存储结构

基于时间的考虑:

  • 顺序表具有随机存取特性,给定序号查找对应元素值的时间为O(1),而链表不具有随机存取特性,只能顺序访问,给定序号查找对应的元素值的时间为O(n)
  • 在顺序表中插入和删除操作时,通常需要平均移动半个表的元素,而在链表中插入和删除操作仅仅需要修改相关结点的指针成员,不必移动结点

结论:若线性表运算主要是查找,很少做插入和删除操作,宜采用顺序表作为存储结构,若频繁地做插入和删除操作,宜采用链表作为存储结构

最后修改:2022 年 05 月 10 日 08 : 06 PM
如果觉得我的文章对你有用,请随意赞赏