链表、栈和队列的实现与总结

一.实现动态数组ArrayList

当数组容量不够，会新创建一个1.5倍容量的数组快照，然后将旧数组的值复制到新数组，然后把数组引用指向新数组。

/**
 * rangeCheck()，检查数组下标是否越界；
 * add()，在某个下标位置添加元素；
 * resize()，动态扩容，当数组容量满或者空闲整个数组的3/4时，重新定义容量；
 * get()，获取某个位置的元素值；
 * set()，设置某个下标的元素值；
 * remove()，移除某个下标对应的值；**/
public class MyArrayList<E> {
    private int size;//数组长度
    private Object elementData[];//保存数组元素
    //无参构造函数
    public MyArrayList(){
        this.elementData=new Object[10];
    }
    //带参构造函数
    public MyArrayList(int initialCapacity){
       if(initialCapacity>=0){
            this.elementData=new Object[initialCapacity];
        }else{
            throw new RuntimeException("非法输入初始化容量："+initialCapacity);
        }
    }
    public int getSize(){
        return size;
    }
    public int getCapacity(){
        return elementData.length;
    }
    public boolean isEmpty(){
        return size == 0;
    }

    public void rangeCheck(int index){
        if(index < 0 || index >= size)
            throw new IllegalArgumentException("Index is Illegal!");
    }

    public void add(int index,E e){
        if(index<0||index>size){
            throw new IllegalArgumentException("index is illegal!");
        }
        if(size==elementData.length){
            resize(elementData.length);
        }
        //把index后的元素后移
        for(int i=size-1;i>index;i--){
            elementData[i+1]=elementData[i];
        }
        elementData[index]=e;
        size++;
    }
    //末尾添加
    public  void add(E e){
        add(size,e);
    }
   private void resize(int minCapacity){
        int newCapacity=minCapacity+minCapacity<<1;
        Object[]newData=new Object[newCapacity];
        for(int i=0;i<size;i++){
          newData[i]=elementData[i];
        }
        elementData=newData;
   }
    public E remove(int index){  // remove data[index] and return the value
        rangeCheck(index);
        E res = (E) elementData[index];
        for(int i = index; i < size-1; i++){
            elementData[i] = elementData[i+1];
        }
        size--;
        elementData[size] = null;//loitering objects  != memory  leak
        return res;
    }
    public E removeLast(){
        return remove(size-1);
    }
    public E removeFirst(){
        return remove(0);
    }
   public E get(int index){
        rangeCheck(index);
        return (E)elementData[index];
   }
   public E getLast(){
       return (E)elementData[size-1];
   }
    public E getFirst(){
        return (E)elementData[0];
    }
   public void set(int index,E e){
        rangeCheck(index);
        elementData[index]=e;
   }

    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        for(int i=0;i<size;i++){
            res.append(elementData[i]);
            if(i!=size-1){
                res.append(",");
            }
        }


        return "MyArrayList{" +
                "elementData=" + res +
                '}';
    }
}

二.实现单链表

用带头结点的结构构造链表容易对链表进行插入删除操作

/**
 * rangeCheck()，检查链表下标是否越界；
 * add()，在某个下标位置添加元素；
 * get()，获取某个位置的元素值；
 * set()，设置某个下标的元素值；
 * remove()，移除某个下标对应的值；**/
public class MySingleList<E> {
    private class node{
        public node next;
        public E val;
        public node(node next,E val){
            this.val=val;
            this.next=next;
        }
        public node(E val){
            this.val=val;
            this.next=null;
        }
        public node(){
            this(null);
        }
    }
    private node Head; //虚拟的头结点
    private int size; //表示链表当前的元素
    //构造函数构造一个头结点
    public MySingleList(){
        Head=new node();
        size=0;
    }
    public int size(){
        return size;
    }
    public boolean isEmpty(){
        return size == 0;
    }

    public void rangeCheck(int index){
        if(index < 0 || index >= size)
            throw new IllegalArgumentException("Index is Illegal!");
    }
    //将val插入索引为index的节点后
    public void add(int index,E val){
        //1.判断索引的合法性
        if(index < 0 || index > size)
            throw new IllegalArgumentException("Index is Illegal!");        //2.遍历到index节点
        node prev=Head;
        while(index>0){
            prev=prev.next;
            index--;
        }
        node node=new node(val);//被插入的节点
        node.next=prev.next;
        prev.next=node;
        size++;
    }
    public void addFirst(E val){
        add(0,val);
    }
    public void addLast(E val){
        add(size,val);
    }
    public E get(int index){
        rangeCheck(index);
        node prev=Head;
        while(index>0){
            index--;
            prev=prev.next;
        }
        return prev.val;
    }
    public E remove(int index){
        rangeCheck(index);
        node prev=Head;
        while(index>0){
            index--;
            prev=prev.next;
        }
        node deleNode=prev.next;
        prev.next=deleNode.next;
        deleNode.next=null;
        size--;
        return deleNode.val;
    }
    public E removeFirst(){
        return remove(0);
    }
    public E removeLast(){
        return remove(size - 1);
    }
    public void  removeElement(E e){
        node prev=Head;
        while(prev.next!=null){
            if(prev.next.val.equals(e)){
                break;
            }
            prev = prev.next;
        }
        node deleNode =prev.next;
        prev.next=deleNode.next;
        deleNode.next=null;
        size--;
    }
    public E getLast(){
        return get(size-1);
    }
    public E getFirst(){
        return get(1);
    }
    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        node cur = Head.next;
        while(cur != null){
            res.append(cur.val + "->");
            cur = cur.next;
        }
        res.append("NULL");

        return res.toString();
    }
}

测试代码及结果

   public static void main(String[] args) {
        MySingleList<Integer> singleList = new MySingleList<Integer>();
        for(int i = 0 ; i < 5 ; i ++){
            singleList.addFirst(i);//头插
        }
        System.out.println(singleList);

        singleList.add(2, 666);
        System.out.println(singleList);

        singleList.remove(2);
        System.out.println(singleList);

        singleList.removeFirst();
        System.out.println(singleList);

        singleList.removeLast();
        System.out.println(singleList);

        singleList.removeElement(2);
        System.out.println(singleList);

        singleList.addLast(888);
        System.out.println(singleList);
    }

三.实现双向链表

public class MyDoubleList<E> {
    private class Node{
        public E val;
        public Node prev;//前驱
        public Node next;//后继

        public Node(E val, Node prev, Node next) {
            this.val = val;
            this.prev = prev;
            this.next = next;
        }
        public Node(E val){
            this(val,null,null);
        }
        public Node(){
            this(null,null,null);
        }

        @Override
        public String toString() {
            return val.toString();
        }
    }
    private Node Head; //虚拟的头结点
    private int size; //表示链表当前的元素
    //构造函数构造一个头结点
    public MyDoubleList(){
        Head=new Node();
        size=0;
    }
    public int size(){
        return size;
    }
    public boolean isEmpty(){
        return size == 0;
    }
    public void rangeCheck(int index){
        if(index < 0 || index >= size)
            throw new IllegalArgumentException("Index is Illegal!");
    }
    public void add(int index,E e){
        if(index < 0 || index > size){
            throw new IllegalArgumentException("Index is Illegal ! ");
        }
        Node pre = Head;
        for(int i = 0; i < index; i++) pre = pre.next;
        Node node = new Node(e);
        Node nxt=pre.next;
        //前置节点的后节点是node，后置节点的前节点是node，node的后置节点是nxt，node的前置节点是pre，注意nxt是不是空节点
        pre.next=node;
        if(nxt!=null)
            nxt.prev=node;
        node.next=nxt==null?null:nxt;
        node.prev=pre;
        size++;
    }
    public void addFirst(E e){
        add(0,e);
    }
    public void addLast(E e){
        add(size,e);
    }
    public E remove(int index){
        rangeCheck(index);
        if(isEmpty())return null;
        //先遍历到删除节点的前一个节点
        Node pre=Head;
        while(index>0){
            index--;
            pre=pre.next;
        }
        Node deleNode=pre.next;//被删除的节点
        pre.next=deleNode.next;
        if(deleNode.next!=null) deleNode.next.prev=pre;
        size--;
        return deleNode.val;
    }
    public E removeFirst(){
        return remove(0);
    }
    public E removeLast(){
        return remove(size-1);
    }

    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();

        Node cur = Head.next;
        while(cur != null){
            res.append(cur.val+ "->");
            cur = cur.next;
        }
        res.append("NULL");

        return res.toString();
    }

    public static void main(String[] args) {
        MyDoubleList<Integer> dulList = new MyDoubleList<Integer>();
        for(int i = 0; i < 5; i++) dulList.addLast(i);
        System.out.println(dulList);

        dulList.removeLast();
        System.out.println(dulList);

        dulList.removeFirst();
        System.out.println(dulList);

        dulList.remove(1);
        System.out.println(dulList);

        dulList.addFirst(-1);
        dulList.add(1,666);
        System.out.println(dulList);
    }

}

四.实现双向循环链表

public class MyLinkedList<E> {
    private class Node{
        public E val;
        public Node prev;
        public Node next;

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

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

        @Override
        public String toString() {
            return val.toString();
        }
    }
    private Node Head;
    private Node tail;
    private int size;
    public MyLinkedList(){
        //自成一环
        Head=new Node();
        tail=Head;
        Head.next=tail;
        Head.prev=tail;
        tail.next=Head;
        tail.prev=Head;
        size=0;
    }
    public int size(){
        return size;
    }
    public boolean isEmpty(){
        return size == 0;
    }
    public void rangeCheck(int index){
        if(index < 0 || index >= size){
            throw new IllegalArgumentException("Index is Illegal ! ");
        }
    }
    //插入的种特殊情况，在尾部插入
    public void addLast(E val){
        Node node = new Node(val);
        node.prev = tail;
        node.next = Head;
        tail.next = node;
        Head.prev = node;
        tail = node;
        size++;
    }
    public void add(int index, E val){
        if(index < 0 || index > size){
            throw new IllegalArgumentException("Index is Illegal ! ");
        }
        //index从0开始
        if(index==size){
            addLast(val);
            return;
        }
        Node pre=Head;
        while(index>0){
            index--;
            pre=pre.next;
        }
        Node newNode=new Node(val);
        newNode.next=pre.next;
        newNode.prev=pre;
        pre.next.prev=newNode;
        pre.next=newNode;
        size++;
    }
    //访问方式：计算index是在head节点向后遍历快，还是向前遍历快
    public E get(int index){
        rangeCheck(index);
        Node cur = Head;
        if(index < (size << 1)){
            for(int i = 0; i < index + 1; i++)cur = cur.next;
            return cur.val;
        }else {
            for(int i = 0; i < index + 1; i++)cur = cur.prev;
            return cur.val;
        }
    }

    public E removeLast(){
        E ret = tail.val;
        tail.prev.next = tail.next;
        tail.next.prev = tail.prev;
        tail = tail.prev;//改变tail
        size--;
        return ret;
    }

    public E remove(int index){
        rangeCheck(index);
        if(index == size - 1){
            return removeLast();
        }
        Node pre = Head;
        for(int i = 0; i < index; i++)pre = pre.next;
        Node delNode = pre.next;

        pre.next = delNode.next;
        delNode.next.prev = delNode.prev;
        size--;
        return delNode.val;
    }
    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        Node cur = Head.next;
        while(cur != Head){
            res.append(cur.val + "->");
            cur = cur.next;
        }
        //res.append("NULL");
        return res.toString();
    }
    public static void main(String[] args) {
        MyLinkedList<Integer>myLinkedList = new MyLinkedList<Integer>();
        for(int i = 0; i < 5; i++){
            myLinkedList.addLast(i);
        }
        myLinkedList.add(0,-1);
        myLinkedList.add(1,999);
        myLinkedList.removeLast();
        System.out.println(myLinkedList);
        myLinkedList.remove(3);
        System.out.println(myLinkedList);
        //注意tail.next指向的是头结点，值为null
        System.out.println(myLinkedList.tail.next.next.val);
        System.out.println(myLinkedList.Head.next.next.val);
        System.out.println(myLinkedList.tail.prev.val);
       //System.out.println(myLinkedList.get(4));
    }

}

五.使用MyArrayList动态数组和链表实现栈

栈的接口

public interface Stack<E> {
    int getSize();
    boolean isEmpty();
    void push(E e);//进栈
    E pop();//出栈
    E peek();//获取栈顶
}

用MyArrayList实现栈

/**用动态数组实现栈**/
public class MyStack<E> implements Stack<E> {
    private  MyArrayList<E>myArrayList;
    public MyStack(int capacity){
        myArrayList=new MyArrayList<E>(capacity);
    }
    public MyStack(){
        myArrayList=new MyArrayList<E>();
    }

    public int getSize() {
        return myArrayList.getSize();
    }

    public boolean isEmpty() {
        return myArrayList.isEmpty();
    }

    public void push(E e) {
        myArrayList.add(e);
    }

    public E pop() {
        return myArrayList.removeLast();
    }

    public E peek() {
        return myArrayList.getLast();
    }
    @Override
    public String toString(){
        StringBuilder res = new StringBuilder();
        res.append("Stack: ");
        res.append('[');
        for(int i = 0 ; i < myArrayList.getSize() ; i ++){
            res.append(myArrayList.get(i));
            if(i != myArrayList.getSize() - 1)
                res.append(", ");
        }
        res.append("] top");
        return res.toString();
    }

    public static void main(String[] args) {
        MyStack<Integer> s=new MyStack<Integer>();
        for(int i=0;i<5;i++){
            s.push(i);
        }
        System.out.println(s);
        s.pop();
        System.out.println(s);
        System.out.println(s.peek());

    }
}

用单链表实现栈

public class MySingListStack<E>implements Stack<E> {
    private MySingleList<E>s;

    public MySingListStack(){
        s=new MySingleList<E>();
    }

    public int getSize() {
        return s.size();
    }

    public boolean isEmpty() {
        return s.isEmpty();
    }

    public void push(E e) {
        s.addFirst(e);
    }

    public E pop() {
        return s.removeFirst();
    }

    public E peek() {
        return s.getFirst();
    }
    @Override
    public String toString(){
        StringBuilder res = new StringBuilder();
        res.append("Stack: top ");
        res.append(s);
        return res.toString();
    }
    public static void main(String[] args) {
        MySingListStack<Integer> s=new MySingListStack<Integer>();
        for(int i=0;i<5;i++){
            s.push(i);
        }
        System.out.println(s);
        s.pop();
        System.out.println(s);
        System.out.println(s.peek());

    }
}

六.使用MyArrayList动态数组和链表实现队列

队列的接口

public interface Queue<E> {
    int getSize();
    boolean isEmpty();
    void enqueue(E e);//入队
    E dequeue();//出队
    E getFront();//获取队首元素
}

用MyArrayList实现队列

public class MyArrayListQueue<E>implements Queue<E> {
    private MyArrayList<E>a;
    public MyArrayListQueue(){
        a=new MyArrayList<E>();
    }
    public MyArrayListQueue(int capacity){
        a=new MyArrayList<E>(capacity);
    }
    public int getSize() {
        return a.getSize();
    }

    public boolean isEmpty() {
        return a.isEmpty();
    }

    public void enqueue(E e) {
        a.add(e);
    }

    public E dequeue() {
        return a.removeFirst();
    }

    public E getFront() {
        return a.getFirst();
    }
    @Override
    public String toString(){
        StringBuilder res = new StringBuilder();
        res.append("Queue: ");
        res.append("front [");
        for(int i = 0 ; i < a.getSize() ; i ++){
            res.append(a.get(i));
            if(i != a.getSize() - 1)
                res.append(", ");
        }
        res.append("] tail");
        return res.toString();
    }

    public static void main(String[] args) {
        MyArrayListQueue<Integer>a=new MyArrayListQueue<Integer>();
        for(int i=0;i<5;i++){
            a.enqueue(i);
        }
        System.out.println(a);
        a.dequeue();
        a.dequeue();
        System.out.println(a.getFront());
    }
}

用单链表实现队列

public class MySingleListQueue<E>implements Queue<E> {
    private MySingleList<E>s;

    public MySingleListQueue(){
        s=new MySingleList<E>();
    }
    public int getSize() {
        return s.size();
    }

    public boolean isEmpty() {
        return s.isEmpty();
    }

    public void enqueue(E e) {
        s.addLast(e);
    }

    public E dequeue() {
        return s.removeFirst();
    }

    public E getFront() {
        return s.getFirst();
    }

    @Override
    public String toString(){
        StringBuilder res = new StringBuilder();
        res.append("top ");
        res.append(s);
        return res.toString();
    }

    public static void main(String[] args) {
        MySingleListQueue<Integer>s=new MySingleListQueue<Integer>();
        for(int i=0;i<5;i++){
            s.enqueue(i);
        }
        System.out.println(s);
        s.dequeue();
        System.out.println(s.getFront());
        s.dequeue();
        System.out.println(s);
    }
}

七.实现循环队列(LoopQueue)

public class LoopQueue<E>implements Queue<E> {
    private Object[]data;
    private int front,rear;
    private int size;
    public LoopQueue(){
        data=new Object[5];
        front=0;
        rear=0;
        size=0;
    }
    //浪费一个单元，令队满特征为 front = (rear +1)%N---空闲单元法
    public LoopQueue(int capacity){
        data=new Object[capacity+1];
        front=0;
        rear=0;
        size=0;
    }
    public int getSize() {
        return size;
    }

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

    public int getCapacity(){
        return data.length-1;
    }
    //改变数组容量
    private void resize(int capacity){
        Object[]newData=new Object[capacity+1];
        for(int i=0;i<size;i++){
            newData[i]=data[(i+front)%data.length];
        }
        data=newData;
        front=0;
        rear=size;
    }
    public void enqueue(E e) {
        //入队操作，rear往后移，如果队满，扩展队列容量
        if(front==(rear+1)%data.length){
            //扩容
            resize(getCapacity()*2);
        }
        data[rear]=e;
        rear=(rear+1)%data.length;
        size++;
    }

    public E dequeue() {
        if(isEmpty()) throw new IllegalArgumentException("Queue is Empty! Can't delete!");
        E e=(E)data[front];
        data[front]=null;
        front=(front+1)%data.length;
        size--;
        if(size == getCapacity()/4 && getCapacity()/2 != 0){
            resize(getCapacity() / 2);
        }
        return e;
    }

    public E getFront() {
        if(isEmpty())
            throw new IllegalArgumentException("Queue is empty.");
        return (E)data[front];
    }
    public E getRear() {
        if(isEmpty())
            throw new IllegalArgumentException("Queue is empty.");
        return (E)data[rear-1];
    }

    @Override
    public String toString(){

        StringBuilder res = new StringBuilder();
        res.append(String.format("Queue: size = %d , capacity = %d\n", size, getCapacity()));
        res.append("front [");
        for(int i = front ; i != rear ; i = (i + 1) % data.length){
            res.append(data[i]);
            if((i + 1) % data.length != rear) res.append(", ");
        }
        res.append("] tail");
        return res.toString();
    }

    public static void main(String[] args) {
        LoopQueue<Integer> queue = new LoopQueue<Integer>();
        for(int i = 0 ; i < 5 ; i ++){
            queue.enqueue(i);
            System.out.println(queue);
            if(i % 2 == 0){ // 0  2  4
                queue.dequeue();
                System.out.println(queue);
            }
        }


    }
}

链表、栈和队列的实现与总结

原文：https://www.cnblogs.com/cmg219/p/12296487.html