（二）线性表 ---→ 顺序表

「爱情、让人受尽委屈。」 2021-12-10 03:15 274阅读 0赞

### 文章目录 ###

*   *  定义
     *  分类
     *  特点
     *  java代码实现

--------------------

## 定义 ##

> 摘抄自 维基百科

**顺序表** 是在计算机内存中以 **数组** 的形式保存的 **线性表**，是指用一组地址连续的存储单元依次存储数据元素的线性结构。

--------------------

## 分类 ##

在数据结构分类中，属于 **逻辑上的线性结构，物理上的顺序存储结构**分支下 。

--------------------

## 特点 ##

底层实现是利用 **数组**，数组名代表首地址，通过计算每个元素占用的字节数，乘以角标，可以快速的算出角标为 `index` 的元素的内存地址。因此，对于顺序存储结构来说，存取操作的时间复杂度为 `O(1)` 。

对于线性表的 **有序** 特点，顺序表的实现很鸡贼，它底层使用的数组，数组本身就是在内存中开辟一片连续的空间，因此，放在其中的元素就是在这一片连续的内存中，所以必然有序。还获得了一种无敌的能力：**随机访问能力**。

鸡贼的实现有序，代价也是有的，在删除和插入的时候，为了维护有序的特点，而底层是连续的一大片空间，在中间进行插入、删除，需要移动大量的元素。\*\*  
优点：

1.  存、取 的复复杂度都是 `O(1)`
2.  不需要额外空间去维护前后元素的关系

缺点：

1.  插入、删除的复杂度都是 `O(n)`
2.  表中元素个数变化较大的时候，造成空间的不确定性，浪费空间

--------------------

## java代码实现 ##

`java`代码实现

/* * listEmpty() 判断线性表是否为空，为空返回 true ，否则返回 false * clearList()将线性表清空，置为空表 * getElem(index)返回线性表中的第 index+1 元素 * setElem(index,elem) 设置线性表中角标为 index 的元素为 elem * getElemIndex(elem) 返回线性表中元素 elem 的下标 index ，返回 -1 代表线性表中没有该元素。 * insertElem(int index,elem) 在线性表的 index 下标处，插入元素 elem * delete(index) 删除并返回线性表中下标为 index 的元素 * length() 返回线性表的长度 * size() 返回线性表中元素的个数 */
    
    import java.util.Arrays;
    
    /** * @author Yaz * @date 2019-07-11 7:41 **/
    @SuppressWarnings("unused")
    public class ArrayList<T> { 
        private int size = 0;
        private int length = 0;
        private T[] arrayList;
    
    
        public ArrayList() { 
    // 底层构造泛型数组，初始容量为10
            arrayList = (T[]) new Object[10];
            length = 10;
        }
    
        public ArrayList(int length) { 
            arrayList = (T[]) new Object[length];
            this.length = length;
        }
    
        public boolean listEmpty() { 
            return size == 0;
        }
    
        public void clearList() { 
            size = 0 ;
            arrayList = null;
        }
    
        public T getElem(int index) { 
            checkIndex(index,false);
            return arrayList[index];
        }
    
    
        public T setElem(int index, T elem) { 
            checkIndex(index,false);
            T temp = arrayList[index];
            arrayList[index] = elem;
            return temp;
        }
    
        public int getElemIndex(T elem) { 
            for (int i = 0; i < size; i++) { 
                if (arrayList[i] == elem || arrayList[i].equals(elem)) { 
                    return i;
                }
            }
            return -1;
        }
    
        public void insertElem(int index, T elem) { 
            checkIndex(index,true);
            ensureCapacity();
            for (int i = size - 1; i >= index; i--) { 
                arrayList[i + 1] = arrayList[i];
            }
            arrayList[index] = elem;
            size++;
    
        }
    
        public T delete(int index) { 
            checkIndex(index,false);
            T temp = arrayList[index];
            for (int i = index; i < size - 1; i++) { 
                arrayList[i] = arrayList[i + 1];
            }
            arrayList[size--] = null;
            return temp;
        }
    
        public int getLength() { 
            return length;
        }
    
        public int getSize() { 
            return size;
        }
    
        private void checkIndex(int index, boolean isInsert) { 
            if (isInsert) { 
                if (index < 0 || index > size) { 
                    throw new RuntimeException("下标越界，下标合法范围：0-" + size);
                }
            }else { 
                if (index < 0 || index >= size) { 
                    throw new RuntimeException("下标越界，下标合法范围：0-" + (size - 1));
                }
            }
        }
    
        private void ensureCapacity() { 
            if (size == length) { 
                length *= 2;
                arrayList = Arrays.copyOf(arrayList, length);
            }
        }
    }

`junit` 测试代码

import org.junit.Before;
    import org.junit.Test;
    
    import static org.hamcrest.Matchers.is;
    import static org.junit.Assert.*;
    
    
    /** * @author Yaz * @Description * @create 2019-07-11 23:09 **/
    public class ArrayListTest { 
    
        private ArrayList<String> arrayList;
    
    
        @Before
        public void setUp() { 
            arrayList = new ArrayList<>();
        }
    
        @Test
        public void listEmpty() { 
            assertTrue(arrayList.listEmpty());
            arrayList.insertElem(0, "aha");
            assertThat(false, is(arrayList.listEmpty()));
        }
    
        @Test
        public void clearList() { 
            assertThat(0, is(arrayList.getSize()));
            arrayList.insertElem(0, "index");
            assertThat(1, is(arrayList.getSize()));
            arrayList.clearList();
            assertThat(0, is(arrayList.getSize()));
        }
    
        @Test(expected = RuntimeException.class)
        public void getElem() { 
            arrayList.getElem(0);
            arrayList.insertElem(3, "aha");
            arrayList.getElem(2);
            arrayList.insertElem(0, "test");
            assertThat(arrayList.getElem(0), is("test"));
    
        }
    
        @Test(expected = RuntimeException.class)
        public void setElem() { 
            arrayList.setElem(0, "update");
        }
    
        @Test
        public void getElemIndex() { 
            assertThat(-1, is(arrayList.getElemIndex("ha")));
            arrayList.insertElem(0, "ha");
            assertThat(arrayList.getElemIndex("ha"), is(0));
            arrayList.insertElem(1, "haa");
            assertEquals(1, arrayList.getElemIndex("haa"));
        }
    
        @Test(expected = RuntimeException.class)
        public void insertElem() { 
            arrayList.insertElem(12, "12");
        }
    
        @Test(expected = RuntimeException.class)
        public void delete() { 
            arrayList.delete(5);
            arrayList.insertElem(0, "test");
            assertThat("test", is(arrayList.delete(0)));
            assertThat(arrayList.getElemIndex("test"), is(-1));
        }
    
        @Test
        public void getLength() { 
            assertThat(10, is(arrayList.getLength()));
            for (int i = 0; i < 11; i++) { 
                arrayList.insertElem(i, "num-" + i);
            }
            assertThat(20, is(arrayList.getLength()));
        }
    
        @Test
        public void getSize() { 
            assertThat(0, is(arrayList.getSize()));
            arrayList.insertElem(0, "apple");
            arrayList.insertElem(1, "dog");
            assertThat(2, is(arrayList.getSize()));
            arrayList.delete(0);
            assertThat(1, is(arrayList.getSize()));
        }
    
    }

--------------------