手写Java中ArrayList集合和链表

手写Java中ArrayList集合和链表

1、手写Java中ArrayList集合
MyArrayList代码

package Test4;

import java.util.Arrays;
import java.util.Objects;

public class MyArrayList<E> {
    private Object[] elementData;
    private int size;//记录元素的个数，记录下一个位置
    private int DEFAULT_CAPACITY=10;
    //1、添加数据
    public boolean add(E e){
        //1、判断是否需要扩容
        if(size==0){//空指针异常问题
            grow();
        }
        if(size==elementData.length){
            grow();
        }
        elementData[size++]=e;
        return true;
    }
    //2、根据索引取数据
    public E get(int index){
        //做越界判断
        checkIndex(index);
        return (E) elementData[index];
    }
    //3、根据索引进行删除
    public E remove(int index){
        checkIndex(index);
        //难点：判断数组中删除元素后，后面有数据要进行移位操作
        //先把要删除的元素取出来，便于以后删除用
        E elementDatum = (E) elementData[index];
        int moveFlag=size-index-1;
        //如果删除的是最后一个元素就不用移位
        if(moveFlag!=0){
            System.arraycopy(elementData,index+1,elementData,index,moveFlag);//将原数组的index+1位拷贝到原数组的index位置上
        }
        //将当前数组的最后一个数据改成null
        elementData[--size]=null;
        return elementDatum;

    }
    //4、拿集合大小
    public int size(){
        return size;
    }
    //5、遍历集合
    public void forEach(MyConsumer<E> action){
        Objects.requireNonNull(action);
        for (int i = 0; i < size; i++) {
            action.accept((E)elementData[i]);
        }

    }
    public void checkIndex(int index){
        if(index<0||index>=size){
            //抛出异常
            throw new IndexOutOfBoundsException(index+"out of max length"+size);
        }
    }

    //扩容函数
    private void grow() {
        if(size==0){
            elementData=new Object[DEFAULT_CAPACITY];
        }else{
            //后面扩容
            elementData= Arrays.copyOf(elementData,elementData.length+elementData.length>>1);//变成原来的1.5
        }
    }

    @Override
    public String toString() {
      //拼接成数组常见的方式
        StringBuilder sb=new StringBuilder();
        sb.append("[");
        for (int i = 0; i < size; i++) {
            E e = (E)elementData[i];
            sb.append(e).append((i==size-1?"":","));
        }
        sb.append("]");
        return sb.toString();
    }
}

测试代码

package Test4;

public class test4 {
    public static void main(String[] args) {
        //手写ArrayList集合
     MyArrayList<String> list=new MyArrayList<>();
        list.add("Java1");
        list.add("Java2");
        list.add("Java3");
        list.add("Java4");
        list.add("Java5");
        list.add("Java6");
        System.out.println(list);
        String a=list.remove(2);
        System.out.println(a);
        System.out.println(list);
        System.out.println(list.get(0));
        System.out.println(list.size());
        list.forEach(s-> System.out.println(s));//遍历厉害
    }
}

2、手写Java中链表
myLinkedLIst代码

package Test6;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class MyLinkedList<E> {
    //定义一个内部类
    private int size;
    Node<E> head=null;
    public static class Node<E>{
        E data;
        Node<E> next;

        public Node(E data, Node<E> next) {
            this.data = data;
            this.next = next;
        }

        public Node() {
        }
    }
    public Node<E> add(){
        //Node<E> head=null;
        Scanner scanner = new Scanner(System.in);
        while(true){
            System.out.println("请您输入当前节点的数据值");
            String data1 = scanner.next();
            if(data1.equals("exit")){
                break;
            }
            //判断是否是头节点
            if(head==null){
                head=new Node(data1,null);
                size++;
            }else{
                //往后面插入节点（尾插法）
                Node<E> temp=head;
                while(temp.next!=null){
                    temp=temp.next;
                }
                //此时temp是尾部节点
                //把当前节点创建出来，加入到尾部节点
                temp.next=new Node(data1,null);
                size++;
            }
        }
        return head;
    }
    //遍历列表
    public void forEach(Node<E> head){

        if(head==null){
            return;
        }
        Node<E> temp=head;
        while(temp!=null){
            System.out.print(temp.data+" ");
            temp=temp.next;
        }
    }
    public  Node<E> reverse(Node<E> head,int left,int right){
        if(head==null||left<1||left>size||right<1||right>size||left==right||left>right){
            return head;
        }
        //1、找出左节点的起始地址
        Node<E> temp=head;
        Node<E> mask=null;
        int index=0;
        List<E> list=new ArrayList<>();
        while(temp!=null){
            index++;
            if(index==left){
                mask=temp;
            }
            //存储数据
            if(index>=left&&index<=right){
                list.add(temp.data);
            }
            if(index==right) break;
            temp=temp.next;
        }
        for(int i=list.size()-1;i>=0;i--){
            mask.data=list.get(i);
            mask=mask.next;
        }
        return head;


    }
}

测试代码

package Test6;

public class Test {
    public static void main(String[] args) {
        MyLinkedList<String> myLink=new MyLinkedList<>();
        MyLinkedList.Node<String> add = myLink.add();
        myLink.forEach(add);
        MyLinkedList.Node<String>add1=myLink.reverse(add,2,5);
        System.out.println();
        myLink.forEach(add1);
    }
}