数据结构之单链表的增删改查（java版）

逃离我推掉我的手 2022-07-15 04:54 159阅读 0赞

talk is cheap，show you zhe code；

/* * 单链表的遍历是从第0个节点开始 沿着next链，一次访问每个节点并且每个节点只能访问一次 * 当头结点head为空时 此链表为空链表 * * 插入操作 * 1空表插入 判断是否为空 插入的节点为该链的头结点 * 2头插入 * Node<T> p = new Node<x,null>;//创建值为x的p结点 * p.next= head; //p.next指向头结点 * head=p; * * 3 */
    public class Node<T> {
        public T data;
        public Node<T> next;
    
        public Node (T data,Node<T> next){
            this.data=data;
            this.next=next;
        }
        public Node(){
            this(null,null);
        }
        public String toString(){
            if(data==null)
                return null;
            return data.toString();
        }
    }

package dataStructure.linkList;
    
    
    
    /* * 头结点 单链表的存储结构中总是带着头结点的，忽略其数据域 */
    public class SingleList<T> {
        public Node<T> head;
    
        public SingleList() {
            this.head = new Node<T>();                        //调用Node的无参构造方法
        }
    
        public SingleList(T[] values) {
            this();                                           // 创建空单链表只有头结点
            Node<T> rear = this.head;
            for (int i = 0; i < values.length; i++) {
                rear.next = new Node<T>(values[i], null);    //为当前结点的next赋值，并将下一结点指向空 即尾插入
                rear = rear.next;                            // 挪到下一结点
            }
        }
    
        public boolean isEmpty() {
            // 头结点 单链表的存储结构中总是带着头结点的，忽略其数据域
            // 头结点为之后为空 则链表为空
            return this.head.next == null;
        }
    
        public T get(int i) {
            Node<T> p = this.head.next;
            for (int j = 0; p != null && j < i; j++) {
                p = p.next; // 获得后一个结点
            }
    
            return (i >= 0 && p != null) ? p.data : null;
        }
    
        public void set(int i) {
        }
    
        public int size() {
            int size=0;
            Node<T> p = this.head.next;
            if(this.head.next==null){    //判断第一个结点是否为空
                return 0;
            }
            do{
                p=p.next;
                size++;
            }while(p!=null);
            return size;
        }
    
        /* * @param the loaction of insert * * @param value * 此处采取了容错措施 若i<0则插入最前 若i>size则插入在尾部 */
        public void insert(int i, T x) {
            if (x == null) {
                throw new NullPointerException("x==null");
            }
            Node<T> front = this.head;
            for (int j = 0; front.next != null && j < i; j++) {
                front = front.next; // 遍历到插入处
            }
            front.next = new Node<>(x, front.next);
        }
        public void insert(T x){
            insert(Integer.MAX_VALUE,x);
        }
    
        public void remove(int i) {
            Node<T> front = this.head;
            for (int j = 0; front.next != null && j < i; j++) {
                front = front.next; // 遍历到i-1处
            }
            if (front.next != null && i >= 0) {
                front.next = front.next.next;
            }
        }
    
        public String toString() {
            String str = this.getClass().getName() + "(";
            for (Node<T> p = this.head.next; p != null; p = p.next) {
                str += p.data.toString();
                if (p.next != null) {
                    str += ",";
                }
            }
            str += ")";
            return str;
        }
    
        public static void main(String[] args) {
            SingleList<String> testhead = new SingleList<String>();
            System.out.println(testhead.head); 
            System.out.println(testhead.head.data);
    
            Integer[] valuesnumber = { 1, 5, 3, 5, 6, 86, 89, 4, 5, 35, 7 };
            String[] values = { "A", "B", "C", "D" };
            SingleList<String> test = new SingleList<String>(values);
    
    
            System.out.println(test.toString()+test.size());
            System.out.println("索引为1 的结点值" + test.get(1).toString());
            test.insert(-1, "insertlocation");
            System.out.println(test.toString());
            test.remove(2);
            test.insert("fd");
            System.out.println(test.toString());
    
            SingleList<Integer> test2 = new SingleList<Integer>(valuesnumber);
            System.out.println(test2.toString());
    
        }
    
    }