一、线性表

1、Interface：MyList

2、Class：MyArrayList

（1）关于MyArrayList的有参构造函数

（2）检验数组是否full的函数ensureCapacity

3、Class：MyLinkedList

二、栈和队列

（1）GenericQueue

（2）GenericStack

三、优先队列

一个月前学习了线性表、栈、队列和优先队列的相关特性和接口、类中的方法。

博客：Java数据结构：线性表、栈、队列和优先队列_颜然的博客-CSDN博客

下面 --> 如何自己实现一个这样的数据结构。

一、线性表

回忆一下Iterable接口，它可以实现一个迭代器。可以使用Iterable.hasNext做while循环参数，即可遍历想要遍历的结构。

1、Interface：MyList

现定义一个Collection接口的子类--MyList接口，去保存MyArrayList（数组型）和LinkedList（链表型）线性表的通用方法：

import java.util.Collection;
//MyList接口
public interface MyList extends Collection {
    // 指定位置添加
    public void add(int index, E e);
    // 返回索引处元素
    public E get(int index);
    // 返回表中第一个匹配元素的索引
    public int indexOf(Object e);
    // 返回表中最后一个匹配元素的索引
    public int lastIndexOf(E e);
    //移除并返回
    public E remove(int index);
    //替换
    public E set(int index, E e);

    @Override
    public default boolean add(E e){
        add(size(), e);
        return true;
    }

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

    @Override
    public default boolean remove(Object e){
        if(indexOf(e) >= 0){
            remove(indexOf(e));
            return true;
        }else return false;
    }

    @Override
    public default boolean containsAll(Collection c){
        return true;
    }

    @Override
    public default boolean addAll(Collection c){
        return true;
    }

    @Override
    public default boolean removeAll(Collection c){
        return true;
    }

    @Override
    public default boolean retainAll(Collection c){
        return true;
    }

    @Override
    public default Object[] toArray(){
        return null;
    }

    @Override
    public default  T[] toArray(T[] array){
        return null;
    }
}

2、Class：MyArrayList

虽说数组一经创建就无法改变大小，但我们依旧可以利用数组去实现动态的数据结构。实现过程中如果数组大小不够，无法继续存储表中新元素时，我们创建一个更大的新数组来代替当前数组：

import java.util.Collection;
import java.util.Iterator;

public class MyArrayList implements MyList{
    public static final int INITIAL_CAPACITY = 16;  // 常量用于创建一个初始数组
    // 泛型限制处理：
    private E[] data = (E[])new Object[INITIAL_CAPACITY];  // 直接创建Object型数组，后强转为E[]型数组即可
    private int size = 0;  // 跟踪线性表元素个数

    public MyArrayList(){
    }

    public MyArrayList(E[] object){
        for(int i = 0; i < object.length; i++){
            add(object[i]);
        }
    }

    // 元素e插入指定下标index处
    @Override
    public void add(int index,E e){
        if(index < 0 || index >size){
            throw new IndexOutOfBoundsException("Index: " + index + " ,Size: " + size);
        }
        ensureCapacity();
        for(int i = size - 1; i >= index; i--){
            data[i+1] = data[i];
        }
        data[index] = e;
        size++;
    }

    // 检验数组是否已满
    private void ensureCapacity(){
        if(size >= data.length){
            E[] newData = (E[])(new Object[size * 2 + 1]);
            System.arraycopy(data, 0, newData, 0,size);  // 复制数组
            data = newData;
        }
    }

    // 创建大小为常量的新数组，size设置为0
    @Override
    public void clear(){
        // 这行删掉，能跑，但会内存泄露。
        // 只有创建了新数组并赋给data，原来data的内容才会被当作垃圾回收掉
        data = (E[])new Object[INITIAL_CAPACITY];
        size = 0;
    }

    // 判读数组中是否包含元素e
    @Override
    public boolean contains(Object e){
        for(int i = 0; i < size; i++){
            if(e.equals(data[i])){ // equals比较
                return true;
            }
        }
        return false;
    }

    // 检查索引index是否在范围内，yes --> 返回索引处元素
    @Override
    public E get(int index){
        checkIndex(index);
        return data[index];
    }

    // 检查索引index是否在范围内，no --> 抛出异常
    private void checkIndex(int index){
        if(index < 0 || index >= size){
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }
    }

    // 从头比较
    @Override
    public int indexOf(Object e){
        for(int i = 0; i < size; i++){
            if(e.equals(data[i])){
                return i;
            }
        }
        return -1;
    }

    // 从尾比较
    @Override
    public int lastIndexOf(E e){
        for(int i = size - 1; i >= 0; i--){
            if(e.equals(data[i])){
                return i;
            }
        }
        return -1;
    }

    // 删除操作
    @Override
    public E remove(int index){
        checkIndex(index); // 检查
        E e = data[index];
        for(int j = index; j< size -1; j++){
            data[j] = data[j + 1];  // 索引之后的元素向左移动
        }
        data[size -1] = null;  // 最后一个置为null
        size--;  // 个数-1
        return e;
    }

    // 替换
    @Override
    public E set(int index,E e){
        checkIndex(index);
        E old = data[index];
        data[index] = e;
        return old;
    }

    // 返回线性表中所有元素的字符串
    @Override
    public String toString(){
        StringBuilder result = new StringBuilder("[");
        for(int i = 0; i < size; i++){
            result.append(data[i]);
            if(i < size - 1){
                result.append(", ");
            }
        }
        return result.toString() + "]";
    }

    // size与capacity不与相等时，可用于修剪数组大小
    public void trimToSize(){
        if(size != data.length){
            E[] newData = (E[])(new Object[size]);
            System.arraycopy(data, 0, newData, 0,size);
            data = newData;
        }
    }

    // 迭代器迭代器
    // 返回一个java.util.Iterator实例
    @Override
    public Iterator iterator(){
        return new ArrayListIterator();
    }

    private class ArrayListIterator implements Iterator{
        private int current = 0;  // 标识被遍历元素的当前位置

        @Override
        public boolean hasNext(){
            return current < size;
        }
        @Override
        public E next(){
            return data[current++];
        }
        @Override
        public void remove(){
            if(current == 0){
                throw new IllegalStateException();
            }
            MyArrayList.this.remove(--current);
        }
    }

    // 返回元素个数
    @Override
    public int size(){
        return size;
    }
}

几个要注意的点：

（1）关于MyArrayList的有参构造函数

函数体中的for循环有两个错误替换方法：

```
super(objects);
```

会抛出 NullPointerException 异常。调用super类的构造函数，将object中的元素添加到data中。但是，data尚未初始化。它将在super类的构造函数主体执行后初始化，此时会得到NullPointerException。

```
data = objects;
size = objects.length;
```

这是一个安全漏洞。data和object引用相同数组，这样能通过object直接更改数组元素来更改MyArrayList，而不能做到独立开。

（2）检验数组是否full的函数ensureCapacity

其中newData的大小无论扩充几倍，我们需要在后面加个数字。如果只是单纯的：

E[] newData = (E[])(new Object[size * 2]);  //（不+1）

会抛出 ArrayIndexOutOfBounds 异常。当执行trimToSize()操作修剪空数组列表其大小将变为0。如果这时通过大小加倍来创建新数组，那么新数组大小仍为0。

3、Class：MyLinkedList

自定义链式线性表：

public class MyLinkedList implements MyList{
    private Node head,tail;
    private int size = 0;

    private static class Node{  // Node结点类
        E element;
        Node next;

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

    public MyLinkedList(){
    }

    public MyLinkedList(E[] objects) {
        for(int i = 0; i < objects.length; i++){
            add(objects[i]);
        }
    }

    public E getFirst(){
        if(size == 0){
            return null;
        }else{
            return head.element;
        }
    }

    public E getLast(){
        if(size == 0){
            return null;
        }else{
            return tail.element;
        }
    }

    
    public void addFirst(E e){
        Node newNode = new Node<>(e);  // 建立一个新结点
        newNode.next = head;  // 将新节点与头链接
        head = newNode;  // 头指向新节点
        size++; // 长度增加

        if(tail == null){
            tail = head;
        }
    }

    
    public void addLast(E e){
        Node newNode = new Node<>(e);

        if(tail == null){  // 多一层判断
            head = tail = newNode; //统一指向
        }else{
            tail.next = newNode;
            tail = newNode;
        }
        size++;
    }

    
    @Override
    public void add(int index, E e){
        if(index == 0){
            addFirst(e);
        }else if(index >= size){
            addLast(e);
        }else{  // 在中间插入：
            Node current = head;
            for(int i = 1; i < index; i++){
                // 定位
                current = current.next;   // next需要一个个接过去
            }
            Node temp = current.next;
            current.next = new Node<>(e); // 前结点
            (current.next).next = temp;  // 后结点
            size++;
        }
    }

    public E removeFirst() {
        Node temp;
        if (size == 0) {
            return null;
        } else {
            temp = head;
            head = head.next;  // 将head指向第二个结点，从而删除第一个
            size--;
            if (head == null) {
                tail = null;
            }
        }
        return temp.element;
    }

    public E removeLast(){
        if(size == 0){
            return null;
        }else if(size == 1){
            Node temp = head;
            head = tail = null;
            size = 0;
            return temp.element;
        }else{  // 销毁最后一个结点
            Node current = head;
            // tail重定位到倒二个结点上
            for(int i = 0;i < size - 2; i++){
                current = current.next;  // 定位操作
            }
            Node temp = tail;
            tail = current;
            tail.next = null;
            size--;
            return temp.element;
        }
    }

    public E remove(int index){
        if(index < 0 || index >= size){
            return null;
        }else if(index == 0){
            return removeFirst();
        }else if(index == size-1){
            return removeLast();
        }else{
            Node previous = head;
            for(int i = 1;i < index;i++){
                previous = previous.next;
            }
            Node current = previous.next;
            previous.next = current.next;
            size--;
            return current.element;
        }
    }

    @Override
    public String toString(){
        StringBuilder result = new StringBuilder("[");

        Node current = head;
        for(int i = 0;i < size;i++){
            result.append(current.element);
            current = current.next;
            if(current != null){
                result.append(",");
            }else{
                result.append("]");
            }
        }
        return result.toString();
    }

    @Override
    public void clear(){
        size = 0;
        head = tail = null;
    }

    @Override
    public boolean contains(Object e){
        return true;
    }

    @Override
    public E get(int index){
        return null;
    }

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

    @Override
    public int lastIndexOf(E e){
        return 0;
    }

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

    @Override
    public java.util.Iterator iterator(){
        return new LinkedListIterator();
    }

    private class LinkedListIterator implements java.util.Iterator{
        private Node current = head;

        @Override
        public boolean hasNext(){
            return (current != null);
        }

        @Override
        public E next(){
            E e = current.element;
            current = current.next;
            return e;
        }

        @Override
        public void remove(){

        }
    }

    @Override
    public int size(){
        return size;
    }
}

二、栈和队列

（1）GenericQueue

基于链表LinkedList，存储队列元素：

class GenericQueue {
    private LinkedList list = new LinkedList<>();

    public void enqueue(E e) {  // add
        list.addLast(e);
    }

    public E dequeue() {  // remove
        return list.removeFirst();
    }

    public int getSize() {  // get size
        return list.size();
    }

    @Override
    public String toString(){  //get string all
        return "Queue: " + list.toString();
    }
}

（2）GenericStack

基于链表LinkedList，存储栈元素：

class GenericStack {
    private LinkedList stack = new LinkedList();
    private int top = 0;

    public int size () {
        return top;
    }

    public void push (T item) {
        stack.add (top++, item);
    }

    public T pop () {
        return stack.remove (--top);
    }
}

使用上面两个类进行测试：

public class TestStackQueue{
    public static void main(String[] args){
        // create a stack
        GenericStack stack = new GenericStack<>();

        stack.push("Tom");
        System.out.println("(1)" + stack);

        stack.push("Susan");
        System.out.println("(2)" + stack);

        stack.push("Meredith");
        stack.push("Mike");
        System.out.println("(3)" + stack);

        System.out.println("(4)" + stack.pop());
        System.out.println("(5)" + stack.pop());
        System.out.println("(6)" + stack);

        // create a queue
        GenericQueue queue = new GenericQueue<>();

        queue.enqueue("Tom");
        System.out.println("(7)" + queue);

        queue.enqueue("Susan");
        System.out.println("(8)" + queue);

        queue.enqueue("Meredith");
        queue.enqueue("Mike");
        System.out.println("(9)" + queue);

        System.out.println("(10)" + queue.dequeue());
        System.out.println("(11)" + queue.dequeue());
        System.out.println("(12)" + queue);
    }
}

三、优先队列
使用堆Heap实现优先队列。普通队列从头取、从尾加。优先队列中，元素被赋予优先级。

Java链表：实现MyArrayList和MyLinkedList

一、线性表

回忆一下Iterable接口，它可以实现一个迭代器。可以使用Iterable.hasNext做while循环参数，即可遍历想要遍历的结构。

二、栈和队列

三、优先队列
使用堆Heap实现优先队列。普通队列从头取、从尾加。优先队列中，元素被赋予优先级。

Java相关栏目本月热门文章

Java链表：实现MyArrayList和MyLinkedList

一、线性表 回忆一下Iterable接口，它可以实现一个迭代器。可以使用Iterable.hasNext做while循环参数，即可遍历想要遍历的结构。

二、栈和队列

三、优先队列 使用堆Heap实现优先队列。普通队列从头取、从尾加。优先队列中，元素被赋予优先级。

Java相关栏目本月热门文章

一、线性表

回忆一下Iterable接口，它可以实现一个迭代器。可以使用Iterable.hasNext做while循环参数，即可遍历想要遍历的结构。

三、优先队列
使用堆Heap实现优先队列。普通队列从头取、从尾加。优先队列中，元素被赋予优先级。