初识数据结构

数组Array:

        自己实现底层，依托的还是jdk底层的静态数组E[] data，数组的实际数组用int size变量维护;

import java.util.ArrayList;
import java.util.Arrays;

public class Array {

//    private int[] data;  // 现在只能承载int型数据
    private E[] data;     // 现在可以承载引用数据类型数据
    private int size;    // 用来描述我的数组中到底有多少个有效的数据

    // 构造函数，传入数组的容量capacity构造Array
    public Array(int capacity){
        data = (E[])new Object[capacity];
        size = 0;
    }
    // 无参构造，默认数组的容量capacity=10
    public Array(){
        this(10);
    }

    //
    public int getSize(){
        return size;
    }

    //
    public int getCapacity(){
        return data.length;
    }

    //返回数组是否为空
    public boolean isEmpty(){
        return size == 0;
    }

    // 尾插 O(1)
    public void addLast(E e){
//        if (size == data.length){
//            throw new IllegalArgumentException("数组已满");
//        }
//        // data[size++] = e;
//        data[size] = e;
//        size++;
        add(size,e);
    }

//    ArrayList
    //头插 O(n)
    public void addFirst(E e){
        add(0,e);
    }

    // 向指定位置添加元素 O(n/2)=>O(n)
    public void add(int index, E e){
       // 对index合法性判断
       if (index < 0 || index > size){
           throw new IllegalArgumentException("index >= 0 and index <= size");
       }
        // 数组容量是否足够
        if (size == data.length){
//            throw new IllegalArgumentException("数组已满");
            resize(2*data.length);
        }
       for (int i = size - 1; i >= index;i--){
           data[i+1] = data[i];
       }
       data[index] = e;
       size++;
    }

    // 获取index索引位置的元素O(1)
    E get(int index){
        if (index < 0 || index >= size){
            throw new IllegalArgumentException("get failed index is illegal");
        }
        return data[index];
    }

    // 修改操作 O(1)
    void set(int index, E e){
        if (index < 0 || index >= size){
            throw new IllegalArgumentException("get failed index is illegal");
        }
        data[index] = e;
    }

    // 查找数组中是否包含元素e
    // O(n)
    public boolean contains(E e){
        for (int i = 0;i= size){
            throw new IllegalArgumentException("get failed index is illegal");
        }
        E ret = data[index];
        for (int i =index +1;i 
链表linkedList:
 
        底层就是维护了一个内部类Node,Node有2个成员变量，一个存放数据的节点E e，还有个就是下一个节点的引用Node next(新new对象的引用，实际上就是这个对象在栈中的地址【指针】)
 
public class linkedList {

//    java.util.linkedList
    private class Node{
        public E e;             // 元素
        public Node next;       // 指针 就是下一个元素的引用

        public Node(E e,Node next){
            this.e = e;
            this.next = next;
        }

        public Node(E e){
            this(e,null);
        }

        public Node(){
            this(null,null);
        }

        @Override
        public String toString(){
            return e.toString();
        }
    }

//    private Node head;
    private Node dummyHead;     // 虚拟头结点
    private int size;

    public linkedList(){
        dummyHead = new Node(null,null);
        size = 0;
    }

    //链表中元素个数
    public int getSize(){
        return size;
    }

    // 返回链表是否为空
    public boolean isEmpty(){
        return size == 0;
    }

    //
//    public void add(int index,E e){
//        if(index < 0 || index > size)
//            throw new IllegalArgumentException("索引越界");
//        if (index == 0)
//            addFirst(e);
//        else {
//            Node prev = head;
//            for (int i = 0;i size)
            throw new IllegalArgumentException("索引越界");
        Node prev = dummyHead;
        for (int i = 0;i size)
            throw new IllegalArgumentException("索引越界");
        Node cur = dummyHead.next;
        for (int i = 0;i size)
            throw new IllegalArgumentException("索引越界");

        Node cur = dummyHead.next;
        for (int i=0;i= size)
            throw new IllegalArgumentException("索引越界");
        Node prev = this.dummyHead;
        for (int i=0;i");
//            cur = cur.next;
//        }
        for (Node cur = dummyHead.next;cur != null;cur = cur.next)
            res.append(cur + "->");
        res.append("NULL");
        return res.toString();
    }

}