寒光博客

[java] 单链表 SingleLinkedList
链表在元素的删除增加方面相比于顺序表时间复杂度是要低的 同样直接继承了MyList的接口 部分问题和自我理解 写了...
扫描右侧二维码阅读全文
26
2019/09

[java] 单链表 SingleLinkedList

链表在元素的删除增加方面相比于顺序表时间复杂度是要低的
同样直接继承了MyList的接口
部分问题和自我理解 写了注释

有几处定义了 per 来存储p的前一个节点的地址 方便跳过p指向p.next 进行删除 增加操作

ListNode

package _09_Linear.list;

/*节点*/

public class ListNode {
    Object data;//数据
    ListNode next;//指向下一个节点的指针

    public ListNode(Object data) {//初始化构造器
        this.data = data;
    }
}

SingleLinkedList

package _09_Linear.list;

public class SingleLinkedList implements MyList {
    ListNode first;//两个指针交互
    ListNode last;
    private int size;

    @Override
    public void add(Object element) {
        //新增一个节点
        if (first == null) {//第一个节点
            first = new ListNode(element);
            last = first;//last==first 所以 first空 存储其他数据
        } else {
            //last.next指向新的节点
            last.next = new ListNode(element);//第一次:last 等价于 first 同一个对象 所以 first.next=last.next or data
            last = last.next;//现在的last是 新元素的节点 其中next等待下次 赋值//所以下一次就是 last.next.next

        }
        size++;//链表存的元素cnt

    }

    @Override
    public void delete(Object element) {
        ListNode p = first;
        ListNode pre = null;//first的前驱为空
        while (p != null) {
            if (p.data.equals(element)) {//当前p 匹配到了
                size--;
                if (p == first) {//【特判】 头指针 为删除目标 特判
                    first = first.next;
                } else {
                    pre.next = p.next;
                }
            }
            pre = p;//记录上一次比对的节点
            p = p.next;//滑动指向下一个节点
        }
    }

    @Override
    public void delete(int index) {
        if (index < 0 || index >= size) {
            return;//索引超出 [0,size)
        }
        int i = 0;
        ListNode p = first;
        ListNode pre = null;//first的前驱为空
        while (p != null) {
            if (i == index) {
                size--;
                if (p == first) {// 【特判】头指针 为删除目标 特判
                    first = first.next;
                } else {
                    pre.next = p.next;
                }
            }
            pre = p;
            p = p.next;
            i++;
        }

    }

    @Override
    public void update(int index, Object newElement) {
        if (index < 0 || index >= size) {
            return;//索引超出 [0,size)
        }
        int i = 0;
        ListNode p = first;
        while (p != null) {
            if (i == index) {
                p.data = newElement;
                break;
            }
            i++;
            p = p.next;
        }
    }

    @Override
    public boolean contains(Object target) {
        ListNode p = first;
        while (p != null) {
            if (p.data.equals(target)) {
                return true;
            }
            p = p.next;
        }
        return false;
    }

    @Override
    public Object at(int index) {
        if (index < 0 && index >= size) {
            return null;
        }
        int i = 0;
        ListNode p = first;
        while (p != null) {
            if (i == index) {
                return p.data;
            }
            p = p.next;
            i++;
        }
        return null;
    }

    @Override
    public int indexOf(Object element) {
        ListNode p = first;
        int i = 0;
        while (p != null) {
            if (p.data.equals(element)) {
                return i;
            }
            p = p.next;
            i++;
        }
        return -1;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder("[");
        ListNode p = first;//头指针
        while (p != null) {//当前数据不是空
            sb.append(p.data).append(p.next != null ? "," : "");//判断是不是最后一个节点
            p = p.next;
        }
        sb.append("]");//这么写的原因是 如果为空 就[] 不然写到while 里面 while不判定就gg
        return "MyArrayList{" +
                "elements=" + sb.toString() +
                "size=" + size +
                '}';
    }
}

Test

package _09_Linear.list;

import org.junit.Test;

public class SingleLinkedListTest {

    SingleLinkedList list = new SingleLinkedList();

    @Test
    public void add() {
        list.add("a");
        list.add("b");
        list.add("c");
        System.out.println(list);
    }

    @Test
    public void delete() {
        add();
        list.delete("a");
        System.out.println(list);
        System.out.println("====");
        list.delete(1);
        System.out.println(list);
        list.delete(0);
        System.out.println(list);
        list.delete(0);
        System.out.println(list);
        list.delete(0);
        System.out.println(list);
    }

    @Test
    public void update() {
        add();
        list.update(2, "hhhhh");
        System.out.println(list);
        list.update(5, "hxx");
        System.out.println(list);
    }

    @Test
    public void contains() {
        add();
        System.out.println(list.contains("a"));
    }

    @Test
    public void at() {
        add();
        System.out.println(list.at(0));
        System.out.println(list.at(5));//null
    }

    @Test
    public void indexOf() {
        add();
        System.out.println(list.indexOf("a"));
        System.out.println(list.indexOf("Dxoca"));
        System.out.println(list.indexOf("c"));
    }

}
Last modification:September 26th, 2019 at 11:10 pm
如果觉得我的文章对你有用,请随意赞赏

Leave a Comment