Destroy an object in objective-C

Question

I'm trying to implement a linked list, so I have a Node class with a header file like so:

@interface Node : NSObject

@property(nonatomic,assign)int data;
@property(nonatomic,strong) Node *right;
@property(nonatomic,strong) Node *left;

@end

Then in another class, I'm allocating them and then calling a method to destroy all occurences of a given value:

Node *node0 = [[Node alloc]init];
Node *node1 = [[Node alloc]init];
Node *node2 = [[Node alloc]init];
Node *node3 = [[Node alloc]init];
Node *node4 = [[Node alloc]init];
node0.data = 1;
node1.data = 2;
node2.data = 5;
node3.data = 5;
node4.data = 3;
node0.right = node1;
node1.right = node2;
node2.right = node3;
node3.right = node4;
node4.right = NULL;
[self removeNodeWithValue:node0 value:5];
NSLog(@"node %d, %d, %d, %d, %d", node0.data, node1.data, node2.data, node3.data, node4.data);

And here's the method itself:

-(void)removeNodeWithValue:(Node *)head value:(int)value
 {
  Node *toDelete;
  while (head != NULL) {
    if (head.data == value)
    {
        toDelete = head;
        head = head.right;
        toDelete = nil;
    }
    else
    {
       head = head.right;
    }
  }
 }
 ==> 1, 2, 5, 5, 3

I know I can change the instances because if I change toDelete = nil to toDelete.data = 4, then the output is ==> 1, 2, 4, 4, 3. My question is, how do I destroy those instances? Thanks.

Answer 1

It seems like you haven't understood how ARC works. As long as there's a strong pointer to the object, the object will not be deallocated. In your example your code fails for two reasons: first of all you always keep a strong reference to node0:

Node *node0 = [[Node alloc]init];

As long as this pointer isn't set to nil (remember, by convention NULL is used for regular pointers, nil for object pointers), the node will not be deallocated.

Second, if the node to be deallocated isn't the first node, then there is another node holding a strong pointer to it, and that's another reason why the node will not be deallocated. Keeping another pointer that points to node0 (toDelete in your case) will increase the node retain count of the node, and when you set it to nil it will just go back to it's original value.

To do it correctly you have also to avoid chain deletion (if the first node gets deallocated it loses the strong reference to the second node, which may get deallocated if there isn't a strong pointer to it, and causes also the third node to be deallocated, and so on).

Finally, I recommend to don't just hold a bunch of pointers to each node, instead implement a linked list class, that will do the job of adding/removing nodes:

@interface List : NSObject

@property (nonatomic, strong) Node* first;
@property (nonatomic, weak) Node* last;

@end

// Inside the class implementation

- (void) addNodeWithValue: (int) value
{
    Node* node= [[Node alloc]init];
    node.data= value;
    if(!first)
    {
        last= first= node;
    }
    else
    {
        last.right= node;
        node.left= last;   // left should be a weak property
        last= node;
    }
}

- (void) removeNodeWithValue: (int) value  // O(n) method
{
    Node* ptr= first;
    while(ptr) 
    {
        if(ptr.data== value)
        {
            if(ptr== first)
            {
                first= last= nil;
            }
            else
            {
                ptr.left.right= ptr.right;
                ptr.right.left= ptr.left;
            }
            break;  // Remove the break if you want to remove all nodes with that value
        }
        ptr= ptr.right;
    }
}

I haven't tested this code, I can't guarantee that it works.

Answer 2

Your problem is not deleting objects, but pointers.

Pointers are like arrows pointing to a box with contents (memory position). When you do

toDelete = head;
head = head.right;
toDelete = nil;

You are just deleting one of the "arrows" that were poiting to some box, but not deleting the box itself.

Wain's answer should give a right approach.

Answer 3

So you want to purge all nodes with a specified value. First off, your test isn't valid because you have explicit references to all of the nodes so even if they were purged from your node structure your test log would still print them out. Secondly, your removal method needs to recursively call through the node structure when it doesn't find that the node under test has the specified value. Thirdly, the node shouldn't test itself, it should test the left and right node values (the node can't remove itself as it doesn't know its parent).

So, something like:

-(void)removeNodeWithValue:(Node *)head value:(int)value
{
    if (head.right.data == value)
    {
       head.right = nil;
    }
    else
    {
        [self removeNodeWithValue:head.right value:value];
    }

    if (head.left.data == value)
    {
       head.left = nil;
    }
    else
    {
        [self removeNodeWithValue:head.left value:value];
    }
}

This doesn't test the root node itself as this should be checked before starting and then remove the head item from the controller itself.