Linked Lists in Objective-C: There’s a Protocol for That!

The interviewer studied my scribbles on the whiteboard.

“Well, your code looks correct—but can you eliminate the special cases?”

The year was 1992, the language was C++, and I was applying for an internship across the lake at Microsoft. I had just finished writing a typical answer to a typical interview question: implement a linked list, with methods to insert nodes at the head and tail, and delete the first node with a given value.

Microsoft interns back then did not get free tablets or private concerts at Gas Works Park, but they did get to throw Bill Gates into his own swimming pool. Standing between me and a backyard barbecue in Medina was bunch of code that looked like this:

void LinkedList::removeValue (void * value) {
  if (!this->head) {
    return;
  }

  if (this->head->value == value) {
    LinkedListNode * zombie = this->head;
    this->head = this->head->next;
    delete zombie;
  }

  for (LinkedListNode * current = this->head; current->next; current = current->next) {
    if (current->next->value == value)
    {
      LinkedListNode * zombie = current->next;
      current->next = zombie->next;
      delete zombie;
      return;
    }
  }
}

(To make my C++ code easier for Objective-C programmers to understand, I have included the syntactic sugar this-> when referencing my instance properties, as the equivalent syntax self. is not optional in Objective-C.)

I thought about the interviewer’s challenge for a minute, and realized that I could use a pointer to a pointer—a double-pointer—to track whose “next” pointer needed to be modified when I removed a node from the list.

void LinkedList::removeValue (void * value) {
  for (LinkedListNode ** current = &this->head; *current; current = &(*current)->next) {
    if ((*current)->value == value)
    {
      LinkedListNode * zombie = *current;
      *current = zombie->next;
      delete zombie;
      return;
    }
  }
}

Satisfied, my interviewer started asking me soft questions about what kinds of programming I enjoyed and what my favorite classes were; the questions you get asked when you have passed the interview but it is not quite time to hand you off to the next interviewer.

Fast forward to September 2015. After leaving Microsoft, I had decided to jump into the world of Apple mobile devices, and I wanted to get up to speed on iOS development quickly. I had heard about Code Fellows in South Lake Union, and I knew they had a good reputation for training new web and iOS developers at all experience levels, so I signed up for their iOS Development Accelerator.

“You have to learn Objective-C. Every iOS development job out there requires Objective-C,” explained Brad, my instructor, at the beginning of the fifth week. “Maybe someday the world will convert over to Swift, but for now…” My fifteen classmates and I groaned. After spending the first month of the class writing in Swift, it was apparently time for us all to grow up.

Okay, let’s see. Header files. Yes, I remember those; I used to use them back in the ’90s. And pointers. Yeah, I remember those too—and all the problems they can cause. “ARC has eliminated most of those problems,” Brad reassured us. “Of course, you can turn off ARC, but we’ll save that for Week 7. For right now, just practice implementing some data structures.”

Stack. Queue. Linked List. The weekly homework assignment read like every job interview I had ever been on. “How hard could this be?” I thought. “Objective-C is based on C, and so is C++, so I should able to bang this out.”

Well, not quite.

It turns out that the very same Objective-C mechanism that saves us from ourselves—ARC—really doesn’t like it when you take the address of a pointer. So my old college trick of using a double-pointer to eliminate the special-case code in the linked list wasn’t going to work.

Luckily, I understood that the C++ technique of taking the address of a variable isn’t really about the address; it’s about obtaining a writeable reference to a variable that can be used to modify the variable’s value without having to know who owns it.

In my case, there were two different variables that I might need to modify, depending on circumstances:

• The head property in the list class itself.
• The next property in the node class.

So then I began to think about how I might persuade two different classes to give me a writeable reference to one of their properties, in a uniform way.

Even though I had only been an iOS developer for a month, and an Objective-C developer for three days, I had already learned that whenever I found myself saying, “I know how to do that on [some other platform], there must be a way in iOS…” the wise oracles of Stack Overflow, Ray Wenderlich, and NSHipster would rise up to sing in chorus:

“There’s a protocol for that!”

Brad had already taught us about protocols in Swift, and I had even written a few of my own for previous homework projects. I knew that protocols are Apple’s answer to polymorphism: giving different classes a uniform interface, so they can be used by other code that doesn’t have to know which specific class is conforming to (implementing) that protocol.

What, exactly, did my protocol need to require of its conforming classes? Well, a node pointer property: specifically, a node pointer property that can be read with a “getter” to walk the list, and that can be changed with a “setter” to point to some other node when inserting or removing a node in the list.

A quick check of the relevant Objective-C syntax persuaded me that I could implement custom getters and setters in my conforming classes to synthesize the protocol’s property any way I wanted, including by redirecting it to another property in the same class.

With that, I was finally able to write a basic linked list in Objective-C with no special-case code for the head node versus other nodes:

//  SettableNodePointer.h

#import <Foundation/Foundation.h>

@class LinkedListNode;

@protocol SettableNodePointer <NSObject>
@property (strong, nonatomic, readwrite) LinkedListNode * node;
@end

---

//  LinkedListNode.h

#import "SettableNodePointer.h"

@interface LinkedListNode : NSObject <SettableNodePointer>
@property (strong, nonatomic) id value;
@property (strong, nonatomic) LinkedListNode * next;

- (instancetype) initWithValue: (id) value;
@end

---

//  LinkedListNode.m

#import "LinkedListNode.h"

@implementation LinkedListNode

// Implement our protocol's "node" property using our "next" property.
- (void) setNode:(LinkedListNode *) newValue {
  self.next = newValue;
}

- (LinkedListNode *) node {
  return self.next;
}

- (instancetype) initWithValue: (id) value {
  self = [super init];
  if (self) {
    self.value = value;
  }
  return self;
}

@end

---

//  LinkedList.h

#import "LinkedListNode.h"

@interface LinkedList : NSObject
- (void) addValueToHead: (id) value;
- (void) addValueToTail: (id) value;
- (void) removeValue: (id) value;
@end

---

//  LinkedList.m

#import "LinkedList.h"

@interface LinkedList () <SettableNodePointer>
@property (strong, nonatomic, readwrite) LinkedListNode * head;
@end


@implementation LinkedList

// Implement our protocol's "node" property using our "head" property.
- (void) setNode: (LinkedListNode *) newValue {
  self.head = newValue;
}

- (LinkedListNode *) node {
  return self.head;
}

// Add "value" to the beginning of the list.
- (void) addValueToHead: (id) value {
  LinkedListNode * newNode = [[LinkedListNode alloc] initWithValue: value];

  newNode.next = self.head;
  self.head = newNode;
}


// Add "value" to the end of the list.
- (void) addValueToTail: (id) value {
  LinkedListNode * newNode = [[LinkedListNode alloc] initWithValue: value];

  id<SettableNodePointer> current = self;
  while (current.node) {
    current = current.node;
  }

  current.node = newNode;
}


// Remove the first instance of "value" from the list.
- (void) removeValue: (id) value {
  for (id<SettableNodePointer> current = self; current.node; current = current.node) {
    if (current.node.value == value)
    {
      current.node = current.node.next;
      return;
    }
  }
}

@end

An Xcode project with the full implementation in Objective-C, including an alternate branch with the original, special-cased code, can be found in this GitHub repository.

For comparison, here is the C++ implementation.