# Swift Algorithm Club: Swift Linked List Data Structure

Learn how to implement a linked list in Swift 3 in this step-by-step tutorial with illustrations and a downloadable example. By Chris Pilcher.

Leave a rating/review
Save for later
Share

## Swift Algorithm Club: Swift Linked List Data Structure

15 mins

The Swift Algorithm Club is an open source project on implementing data structures and algorithms in Swift.

Every month, Kelvin Lau and I feature a cool data structure or algorithm from the club in a tutorial on this site. If you want to learn more about algorithms and data structures, follow along with us!

In this tutorial, you’ll learn how to implement a linked list in Swift 3. The linked list implementation was first implemented by Matthijs Hollemans, the founder of the Swift Algorithm Club.

Note: New to the Swift Algorithm Club? Check out our getting started post first.

## Getting Started

A linked list is a sequence of data items, where each item is referred to as a `node`.

There are two main types of linked lists:

Singly linked lists, are linked lists where each node only has a reference to the next node.

Doubly linked lists, are linked lists where each node has a reference to the previous and next node.

You need to keep track of where the list begins and ends. That’s usually done with pointers called head and tail.

## Linked List Implementation in Swift 3

In this section, you’ll implement a linked list in Swift 3.

Remember that a linked list is made up of nodes. So to start, let’s create a basic node class. Create a new Swift playground and add the following empty class:

```public class Node {

}
```

### Value

A node needs a value associated with it. Add the following between the curly braces:

```var value: String

init(value: String) {
self.value = value
}
```

You’ve declared a property named `value` of type `String`. In your own apps, this could be any datatype you want to store.

You also declare an initializer, which is required for initializing all non-optional stored properties for your class.

### Next

In addition to a value, each node needs a pointer to the next node in the list.

To do this, add the following property to the class:

```var next: Node?
```

You have declared a property named `next` of type `Node`. Note that you’ve made `next` an optional. This is because the last node in the linked list does not point to another node.

### Previous

You are implementing a doubly-linked list so we also need a pointer to the `previous` node in the list.

To do this, add one last property to the class:

```weak var previous: Node?
```

Note: To avoid ownership cycles, we declare the `previous` pointer to be weak. If you have a node `A` that is followed by node `B` in the list, then `A` points to `B` but also `B` points to `A`. In certain circumstances, this ownership cycle can cause nodes to be kept alive even after you deleted them. We don’t want that, so we make one of the pointers weak to break the cycle.

Now that you have created the `Node` you also need to keep track of where the list begins and ends.

To do this, add this new `LinkedList` class to the bottom of the playground:

```public class LinkedList {
private var tail: Node?

public var isEmpty: Bool {
}

public var first: Node? {
}

public var last: Node? {
return tail
}
}
```

This class will keep track of where the list begins and ends. It will also provide a number of other helper functions.

### Append

To handle appending a new node on your list, you’ll declare a `append(value:)` method in your `LinkedList` class. Add the following new method to `LinkedList`:

```public func append(value: String) {
// 1
let newNode = Node(value: value)
// 2
if let tailNode = tail {
newNode.previous = tailNode
tailNode.next = newNode
}
// 3
else {
}
// 4
tail = newNode
}
```

Let’s review this section by section:

• Create a new `Node` to contain the value. Remember, the purpose of the `Node` class is so that each item in the linked list can point to the previous and next node.
• If tailNode is not nil, that means there is something in the linked list already. If that’s the case, configure the new item to point to the tail of the list as it’s previous item. Similarly, configure the new last item on the list to point to the new node as it’s next item.
• Finally, set the tail of the list to be the new item in either case.

Let’s try out your new linked list. Outside the implementation of `LinkedList`, write the following into your playground:

```let dogBreeds = LinkedList()
dogBreeds.append(value: "Bulldog")
dogBreeds.append(value: "Beagle")
dogBreeds.append(value: "Husky")
```

After defining the list, we will try print the list to the console:

```print(dogBreeds)
```

You can bring up the console by pressing the following keys in combination: Command-Shift-Y. You should see the following printed out to the console:

```LinkedList
```

That isn’t very helpful. To display a more readable output string, you can make `LinkedList` adopt the `CustomStringConvertable` protocol. To do this, add the following just below the implementation of your `LinkedList` class:

```// 1
// 2
public var description: String {
// 3
var text = "["
// 4
while node != nil {
text += "\(node!.value)"
node = node!.next
if node != nil { text += ", " }
}
// 5
return text + "]"
}
}
```

Here’s how the code works:

1. You’ve declared an extension to your `LinkedList` class, and you’ve adopted the `CustomStringConvertible` protocol. This protocol expects you to implement a computed property with the name `description`, with the `String` type.
2. You’ve declared the `description` property. This is a computed property, a read only property that returns a `String`.
3. You’ve declared a `text` variable. This will hold the entire string. For now, it contains an opening brace to represent the start of the list.
4. You then loop through the list appending the value of each item to the `text` string.
5. You add a closing brace to the end of the `text` variable.

Now, when you call print on your `LinkedList` classes, you’ll get a nice representation of your list like this:

```"[Labrador, Bulldog, Beagle, Husky]"
```
Chris Pilcher

Chris Pilcher

Author