Linked List Implementation — Swift 4

Append, Prepend, Remove, Find, and Replace

As you may have heard the term linked list pop in every now and then. It’s a form of data structure that can store a collection of items. Linked list consists of a group of nodes together to represent a sequence, relative of the same type.
If you are here to learn how to implement linked lists in Swift and learn some tips, you’re in the right place!

each rectangle represents a node

As you might have guessed, the picture above demonstrates a linked list. In this case, the linked list contains many nodes, a head, and a tail. The head represents the beginning node and the tail represents the last node in the linked list. Each node contains a value(data) and a next referencing to a new node.

Node class contains: value, and next

Linked List class contains: head, and tail

We conform to the ‘Equatable protocol’ in both classes.
Equatable protocol — has a constraint where you are able to check equality between objects of the same type. Thus, allows us to perform the == operation on our T type, and on our Nodes!!

Now that we have our foundation written down, we can start implementing different methods to our LinkedList class👇🏼👇🏼👇🏼

Methods in LinkedList class

I highly recommend to try coding these functions or writing down pseudocode before looking at the solutions!! 📝 ✍🏼

• Prepend (Insert at beginning)
  Runtime: O(1)

1. Create a new node from our input value
2. If our linked list is empty, assign head and tail to our new node
3. If our linked list is not empty:
   assign our new node’s next pointer to self.head
   and update the head pointer to be our new node

• Append at end
  Runtime: O(1)

1. Create a new node from our input value
2. If our linked list is empty, assign head and tail to our new node
3. If our linked list is not empty:
   set the tail’s next pointer to the new node
   and update the tail pointer to be our new node

• Remove a value
  Runtime: O(n) where n is the number of nodes we have to traverse through

In the code below, we are checking for the following cases where we want to remove the node:
case1 : is the tail
case2 : is the head
case3 : is in between nodes
case4 : is the only node (both head and tail)

removing last node (lines 64–70)

removing first node (line 77)

removing middle node (line 70)

removing single node (lines 71–77)

1. Create variables so we have access to the current node and previous node
2. Traverse through the linked lists while current is not nil
3. Found a node that is equal to our input value!!
4. Checking the previous node has a value
5. Deleting a node at the end of a linked list
   set self.tail to be the previous node
6. Change pointer of prev’s next to curr’s next
7. Else, previous node is nil. And we’re deleting a node at the end of a linked list.
   set self.tail to be the previous node
8. Changing self.head to be the current’s next node
9. Haven’t found the item yet, so we keep looping through and checking the next node.

• Length
  Runtime: O(n) where n is the number of nodes in the linked list.
  However, the runtime can be O(1) if we have another value in the linked list class that keeps count of items as we insert/append, or remove.

1. If the linked list is empty, return 0 and leave the function
2. Create variables for count and current node
3. Traverse through the linked list while curr isn’t nil
4. Increment count by 1 and check on the next node
5. Return the count!

• Last element
  Runtime: O(1)

Returns the last element in our linked list.

• Find
  Runtime: O(n) where n is the number of nodes we traverse through.

Here we are traversing through the linked list until we find a node that is equal to our input value.
This method returns the value of that node being that it is found, else, will return nil

• Replace an old item with a new item
  Runtime: O(n) where n is the number of nodes we traverse through.

1. Create a variable to keep count of the current node
2. Traverse through the linked list while curr isn’t nil
3. We’ve found the node! So replace the curr’s value with the new input value and return out of the function
4. Haven’t found the node yet, so we loop to check the next node

Testing

Now that we have our foundation class written down and functioning, let’s go ahead and test to see if these methods actually work 🤔🤔

Append
Start off by instantiating an empty linked list and appending items to it.

let ll = LinkedList<String>()
ll.append(value: "apple")
ll.append(value: "butter")
ll.append(value: "cinnamon")

If we write a print statement checking the head and tail, it should print out “apple” and “cinnamon” respectively.

print(ll.head?.value ?? "no head found")   // apple
print(ll.tail?.value ?? "no tail found")   // cinnamon

Remove
Removing something from the start of a linked list should change the head pointer…

ll.remove(value: "apple")
print(ll.head?.value ?? "nothing found")    // butter
print(ll.tail?.value ?? "no tail found")    // cinnamon

Replace
Replaces the old value with our new value and should print out the new value.

ll.replace(old: "cinnamon", new: "chocolate")
print(ll.tail?.value ?? "no tail found")    // chocolate

These are just some methods of a linked list class implemented in Swift. Go ahead and try these out in a Swift playground and see the magic! Ѻ→Ѻ→Ѻ
I’m sure there are more methods out there and would love to see anyone share them down below😃🤓

Thank you for checking out this blog post! If you have any questions or comments, please feel free to reach out to me 🙂 And don’t forget to give this article some claps! 👏🏼👏🏼*up to 50x*👏🏼 if you found it helpful.💡