链表删除结点操作

2018-11-08 本文已影响32人人魔七七

前提

这个链表不存在重复值的结点

思路

找到这个结点
操作被删除结点的前后指针

复杂度

O(n) 因为你要找到这个结点

代码

- (void)removeObject:(NSObject *)linkData
{
   
    //分两步 第一步找到当前结点 第二步删除操作
    //声明被删除的结点
    DSNode *deleteNode;
    
    if (linkData)
    {
        //当前指针指向头部结点
        self.current = self.head;
        //跳出条件是当前结点 是 nil
        while (self.current != nil)
        {
            //如果当前结点的值 和 要删除的值一样 就找到了要删除的结点
            if ([self.current.linkData isEqual:linkData])
            {
                deleteNode = self.current;
                break;
                
            }
            self.current = self.current.next;

        }
    }
   //找到被删除结点的前后结点 重新操作前后结点的指针 然后把删除的结点nil 分三种情况头部 尾部 以及中间位置
    DSNode *priorNode = deleteNode.prior;
    DSNode *nextNode = deleteNode.next;
    
    if (priorNode == nil)
    {
        self.head = nextNode;
        self.head.prior = nil;
        
    }
    else if (nextNode == nil)
    {
        
        self.tail = priorNode;
        self.tail.next = nil;
    }
    else
    {
        priorNode.next = nextNode;
        nextNode.prior = priorNode;
    }
    deleteNode = nil;
    deleteNode.prior = nil;
    deleteNode.next = nil;
    _count --;
    
}