数据结构1-3(单链表)

wuchangjian2021-11-04 20:21:50编程学习

实现单链表:

1.首先列出单链表的功能(增、删、改、查) 使用接口来定义功能。

2.实现接口,实现单链表的功能

public interface MySingleList {
    void add(Object element);
    void delete(Object element);
    void delete(int index);
    void updata(int index,Object newElement);
    boolean contain(Object target);
    Object at(int index);
    int Indexof(Object element);
}
public class ListNode {
    protected Object data;
    protected ListNode next;

    public ListNode(Object data){
        this.data = data;
    }
}
public class SingleLinkedList implements MySingleList {
    private ListNode head;
    private ListNode last;
    private int size;
    @Override
    public void add(Object element) {
        if (head ==null) {
            head = new ListNode(element);
            last = head;
        }else {
            last.next = new ListNode(element);
            last = last.next;
        }
        size++;
    }

    @Override
    public void delete(Object element) {
        ListNode p = head;
        ListNode pre = null;
        while (p!=null){
        if (p.data.equals(element)) {
            if (p == head)
                head = head.next;
            else
                pre.next = p.next;
                break;
        }
        pre = p;
        p = p.next;
        }
    size--;
    }

    @Override
    public void delete(int index) {
        if (index<0 || index>size){
            return;
        }
        int i = 0;
        ListNode p = head;
        ListNode pre = null;
        while (p != null){
        if (i == index){
            if(p == head){
            head = head.next;
            }else {
                pre.next = p.next;
                break;
            }
        }
            i++;
            p = p.next;
            pre = pre.next;
        }
        size--;
    }

    @Override
    public void updata(int index, Object newElement) {
        int i = 0;
        ListNode p = head;

        while (p != null){
            if(i == index){
                p.data = newElement;
            }else {
                i++;
                p = p.next;
            }
        }

    }

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

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

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

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder("[");
        ListNode p = head;
        while (p!=null){
            sb.append(p.data);
            if (p.next!=null){
                sb.append(",");
            }
            p = p.next;
        }
        sb.append("]");
        return sb.toString();
    }
}

相关文章

[react-router] react的路由和普通路由有什么区别?

[react-router] react的路由和普通路由有什么区别? R...

zset类型的底层数据结构的实现

zset类型的底层数据结构的实现

参考资料: redis中zset底层实现原理_渣渣-CSDN博客_zse...

c++ 虚函数与多态

//允许将子类类型的指针赋值给父类类型的指针。调用同名函数却会因上下文的不同而有不同的实...

发表评论    

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。