数组及链表的增删改查

CURD 增删改查

1、动态数组 链表(单链表，双向链表)

        数组：适合查询

        链表：适合插入，删除

        数组的增删改查：

package com.fyb.oop.week3;

public class MyArrayList1 {
    private Object[] a;
    private int size;
    private static final int INITCAP=10;//初始值
    private static final int INITSIZE=0;
    private static final double LOADNUM=0.75;//阈值，加载因子：不等满就扩容

    public MyArrayList1(){
        a = new Object[INITCAP];
        size = INITSIZE;
    }

    public MyArrayList1(int cap) {
        a = new Object[cap];
        size = INITSIZE;
    }

    //判断数组大小,扩容
    private void expandCap(){
        if (this.size>=a.length*LOADNUM){
            Object[] temp = new Object [a.length<<1];//扩容1倍
            for(int i=0;i<=size;i++){
                temp[i]=a[i];
                a = temp;
            }
        }
    }

    //添加
    public void add(Object n){
        expandCap();
        a[size++] = n;
    }

    //插入
    public void insert(int index,Object n){
        expandCap();
        for (int i=size;i>index;i--){
            a[i] = a[i-1];
        }
        a[index] = n;
        size++;
    }

    //删除
    public T delete(int index){
        T temp = (T)a[index];
        for (int i=index;i 
        单链表的增删改查：
 
public class MylinkedList {
    private Node first;
    private int size;
    private static final Node FIRSTDEFALULT=null;
    private static final int FIRSTDEFAULT=0;

    public MylinkedList() {
        first = FIRSTDEFALULT;
        size = FIRSTDEFAULT;
    }

    //添加
    public void add(Object obj){
        Node node = new Node(obj);
        if(first==null){
            first=node;
        }else{
            Node lastNode = first;
            while (lastNode.getNext()!=null){
                lastNode = lastNode.getNext();
            }
            lastNode.setNext(node);
        }
        size++;
    }

    //插入,在obj1后插入obj2
    public void insert(Object obj1,Object obj2){
        Node node2 = new Node(obj2);

        Node node = first;
        while (node.getNext()!=null&&!node.getValue().equals(obj1)){
            node = node.getNext();
        }
        node2.setNext(node.getNext());
        node.setNext(node2);
        size++;
    }

    //删除
    public T delete(Object obj){
        if(first==null){
            return null;
        }
        if(first.getValue().equals(obj)){
            return (T)first.getValue();
        }
        Node node = first;
        while (!node.getValue().equals(obj)){
            node = node.getNext();
        }
        T t = (T)node.getNext().getValue();
        node.setNext((node.getNext().getNext()));
        size--;
        return t;
    }

    //修改
    public void update(Object obj1,Object obj2){
        Node node = first;
        while (!node.getValue().equals(obj1)){
            node = node.getNext();
        }
        node.setValue(obj2);
    }

    //查询
    public int size(){
        return size;
    }

    //遍历
    public void show(){
        Node currentNode = first;
        if(currentNode==null){
            System.out.println("空链表");
        }else{
            while (currentNode.getNext()!=null){
                System.out.print(currentNode.getValue()+"  ");
                currentNode = currentNode.getNext();
            }
            System.out.print(currentNode.getValue()+"  ");
        }
    }
 
        双向链表的增删改查：
 
public class MylinkedList {
    private Node first;
    private int size;
    private Node last;
    private static final Node FIRSTDEFALULT = null;
    private static final int FIRSTDEFAULT = 0;

    public MylinkedList() {
        first = FIRSTDEFALULT;
        size = FIRSTDEFAULT;
        last = FIRSTDEFALULT;
    }

    //添加
    public void add(Object obj) {
        Node node = new Node(obj);
        if (first == null) {
            first = node;
        } else {
            Node lastNode = first;
            while (lastNode.getNext() != null) {
                lastNode = lastNode.getNext();
            }
            lastNode.setNext(node);
            lastNode.getNext().setPre(node);
        }
        size++;
    }

    //插入,在obj1后插入obj2
    public void insert(Object obj1, Object obj2) {
        Node node2 = new Node(obj2);

        Node node = first;
        while (!node.getValue().equals(obj1)) {
            node = node.getNext();
        }
        node2.setNext(node.getNext());
        node.setNext(node2);
        node2.setPre(node);
        node2.getNext().setPre(node2);
        size++;
    }

    //删除
    public T delete(Object obj) {
        if (first == null) {
            return null;
        }
        if (first.getValue().equals(obj)) {
            return (T) first.getValue();
        }
        Node node = first;
        while (!node.getValue().equals(obj)) {
            node = node.getNext();
        }
        T t = (T) node.getNext().getValue();
        node.getNext().getNext().setPre(node);
        node.setNext((node.getNext().getNext()));
        size--;
        return t;
    }

    //修改
    public void update(Object obj1, Object obj2) {
        Node node = first;
        while (!node.getValue().equals(obj1)) {
            node = node.getNext();
        }
        node.setValue(obj2);
    }

    //查询
    public int size() {
        return size;
    }

    //遍历
    public void show() {
        Node currentNode = first;
        if (currentNode == null) {
            System.out.println("空链表");
        } else {
            while (currentNode.getNext() != null) {
                System.out.print(currentNode.getValue() + "  ");
                currentNode = currentNode.getNext();
            }
            System.out.print(currentNode.getValue() + "  ");
        }
    }
}