Linked Lists

A linked list is a basic data structure that provides a way to associate related content. At a basic level, linked lists provide the same functionality as an array. That is, the ability to insert, retrieve, update and remove related items. However, if properly implemented, linked lists can provide additional flexibility. Since objects are managed independently (instead of contiguously - as with an array), lists can prove useful when dealing with large datasets.

How it works

In its basic form, a linked list is comprised of a key and an indicator. The key represents the data you would like to store such as a string or scalar value. Typically represented by a pointer, the indicator stores the location (also called the address) of where the next item can be found. Using this technique, you can chain seemingly independent objects together.

The Data Structure

Here's an example of a "doubly" linked list structure written in Swift. In addition to storing a key, the structure also provides pointers to the next and previous items. Using generics, the structure can also store any type of object and supports nil values. The concept of combining keys and pointers to create structures not only applies to linked lists, but to other items like tries, queues and graphs.

//generic doubly linked list structure 
class LLNode<T> {
    var key: T?
    var next: LLNode?
    var previous: LLNode?
}

Using Optionals

When creating algorithms its good practice to set your class properties to nil before they are used. Like with app development, nil can be used to determine missing values or to predict the end of a list. Swift helps enforce this best-practice at compile time through a new paradigm called optionals. For example, the function printAllKeys employs an implicit unwrapped optional (e.g., current) to iterate through linked list items.

//print all keys for the class
func printAllKeys() {
    var current: LLNode! = head;
    //assign the next instance
    while (current != nil) {
        println("link item is: \(current.key)")
        current = current.next
    }
}

Adding Links

Here's a simple function that creates a doubly linked list. The method addLink creates a new item and appends it to the list. The Swift generic type contraint <T: Equatable> is also defined to ensure instances conform to a specific protocol.

public class LinkedList<T: Equatable> {

    //create a new LLNode instance
    private var head: LLNode<T> = LLNode<T>()

    //append a new item to a linked list
    func addLink(key: T) {
        //establish the head node
        if (head.key == nil) {
            head.key = key;
            return;
        }
        //establish the iteration variables
        var current: LLNode? = head
        while (current != nil) {
            if (current?.next == nil) {
                var childToUse: LLNode = LLNode<T>()
                childToUse.key = key;
                childToUse.previous = current
                current!.next = childToUse;
                break;
            }
            current = current?.next
        } //end while
    } ///end function

Removing Links

Conversely, here's an example of removing items from a list. Removing links not only involves reclaiming memory (for the deleted item), but also requires reassigning links so the chain remains unbroken.

    //remove a link at a specific index
    func removeLinkAtIndex(index: Int) {
        var current: LLNode<T>? = head
        var trailer: LLNode<T>?
        var listIndex: Int = 0

        //determine if the removal is at the head
        if (index == 0) {
            current = current?.next
            head = current!
            return
        }

        //iterate through the remaining items
        while (current != nil) {
            if (listIndex == index) {
                //redirect the trailer and next pointers
                trailer!.next = current?.next
                current = nil
                break;
            }

            //update the assignments
            trailer = current
            current = current?.next
            listIndex++
        } //end while
    } //end function

Counting Links

When implemented, it can also be convenient to count items. In Swift, this can be expressed as a computed property. For example, the following technique will allow a linked list instance to use a dot notation. (e.g., someList.count)

    //the number of linked items
    var count: Int {
        if (head.key == nil) {
            return 0
        }
        else {
            var current: LLNode = head
            var x: Int = 1

            //cycle through the list of items
            while ((current.next) != nil) {
                current = current.next!;
                x++
            }
            return x
        }
    } //end property

Efficiency

Linked lists as shown typically provide O(n) for storage and lookup. As we'll see, linked lists are often used with other structures to create new models. Algorithms with an efficiency of O(n) are said to run in “linear time”.