首页 > 代码库 > DSA——链表笔记【删除(3个),添加(2个),查找】【循环链表-画个图就明确了】

DSA——链表笔记【删除(3个),添加(2个),查找】【循环链表-画个图就明确了】

几个容易忽视的点儿,这里记一下

删除结点中,删除特定元素值结点及删除尾结点 都需要通过循环找到!注意!没有循环体,找到即可!!

一、删掉info=el的结点【注意链表为空!和只有一个结点!!】

 
public void delete(int el)
    {
        LinkedNode prev=null,temp=null;

        if(isEmpty()) return;//第一步就是判断是不是空链表

        if(head==tail&&head.info==el)//如果只有一个结点,且 结点元素等于el

           head=tail=null;
      //上一步已经把只有一个结点的解决了,下面是节点数>=2的了

        else if(head.info==el)//头结点元素值=el

           head=head.next;

        else//非头结点

        {
          for(prev=head,temp=head.next;temp!=null||temp.info==el;prev=prev.next,temp=temp.next);//找到该结点,并记录其前一个结点
          //这个为什么需要两个 引用 才行呢??如果单单是确保info=el,就不能记录前一个结点了,无法把tail赋值给它了
                if(temp!=null)//!=null说明找到了
                {
                    prev.next=temp.next;//先删除
                    if(temp==tail)//如果这个点恰好是尾结点,别忘了把tail赋值
                        tail=prev;
                }
         
        }
    }
        

删除头结点【注意链表只有一个结点】

public int deleteFromHead()
    {
        //不必判断是不是空链表了,因为即使判断了,该返回什么呢?返回哪个数都不合适,就让用户在使用之前自个做判断吧
        //先记录一下要返回的值吧
        int el=head.info;
        if(head==tail)//如果只有一个结点
            head=tail=null;
        else head=head.next;
        return el;
    }

删除尾结点【还是注意链表只有一个结点】

public int deleteFromTail()
    {
        int el=tail.info;
        if(head==tail)
            head=tail=null;
        else
        {
            LinkedNode temp=null;
            //for(LinkedNode pre=head,temp=head.next;temp!=tail;pre=pre.next,temp=temp.next)
            for(temp=head;temp.next!=tail;temp=temp.next);
///这个则是,只要保证temp的下一个事tail,就好了
tail
=temp; tail.next=null; } }

 

二、链表添加新结点

链表头加一个结点


    public void addToHead(int el)
    {
        head=new LinkedNode(el,head);
//        LinkedNode temp=new LinkedNode(el);
//        temp.next=head;
//        head=temp;
        
        if(tail==null)//不能用if(isEmpty()),因为此时已经添加一个结点了,不是空链表了
            tail=head;
    }

链表尾加一个结点

public void addToTail1(int el)
    {
        LinkedNode temp=new LinkedNode(el);
        if(!isEmpty())
        {
            tail.next=temp;
            tail=tail.next;
        }
        else head=tail=temp;
    }

错误实例

    public void addToTail2(int el)
    {
        LinkedNode temp=new LinkedNode(el);
        tail.next=temp;//这步有严重错误!!如果tail==null,那么就没有tail.next!!将会引发空指针异常!!只有判断是否为空以后!!!才能更改tail.next
        tail=temp;
        if(head==null)
            head=tail;
    }

三、查找:【非常巧妙】

for(temp=head;temp!=null&&temp.info!=el;temp=temp.next);
            return temp!=null;

 循环链表

看笔记吧,懒得整理了··如果下次看发现忘了再整理

DSA——链表笔记【删除(3个),添加(2个),查找】【循环链表-画个图就明确了】