DS & Algorithm (Linked List)

Linked List
  1. Hold a value
  2. Hold a reference to the next node. A nil value represents the end of the list
Figure 1
Figure 2
Figure 3
Figure 4

push operations

  • create Node class , that represent element in the list which has two property actual value and reference to new node
  • Then we create a Linked List class that has head represent first element in list and tail represent last element in list
  • On push operation we need to add element at first which means new item become head
  • New item next item will be the previous head we have
  • if tail is null means currently list is empty so first or newly added item is head and tail both
Figure 5

append operations

  • if the list is empty, you’ll need to update both head and tail to the new node. Since append on an empty list is functionally identical to push, you simply invoke push to do the work for you.
  • In all other cases, you simply create a new node after the tail node. Force unwrapping is guaranteed to succeed since you push in the isEmpty case with the above guard statement.
  • Since this is tail-end insertion, your new node is also the tail of the list.
Figure 6

node(at:)

  1. You create a new reference to head and keep track of the current number of traversals.
  2. Using a while loop, you move the reference down the list until you’ve reached the desired index. Empty lists or out-of-bounds indexes will result in a nil return value.
Figure 7

insert(after:) operations

  1. Finding a particular node in the list.
  2. Inserting the new node
Figure 8
  1. In the case where this method is called with the tail node, you’ll call the functionally equivalent append method. This will take care of updating tail.
  2. Otherwise, you simply link up the new node with the rest of the list and return the new node.
Figure 9

Performance analysis

pop operations

  1. pop returns the value that was removed from the list. This value is optional, since it’s possible that the list is empty.
  2. By moving the head down a node, you’ve effectively removed the first node of the list.
  3. ARC will remove the old node from memory once the method finishes, since there will be no more references attached to it.
  4. In the event that the list becomes empty, you set tail to nil.
Figure 10

removeLast operations

Figure 11
  1. If head is nil, there’s nothing to remove, so you return nil.
  2. If the list only consists of one node, removeLast is functionally equivalent to pop. Since pop will handle updating the head and tail references, you’ll just delegate this work to it.
  3. You keep searching for a next node until current.next is tail which means we reached to node 4
  4. Since current is the second last node we make this as tail and make next to nil which ARC auto free memory
Figure 12

remove(after:) operations

Figure 13

Performance analysis

Figure 14

Becoming a Swift collection

Figure 15

Conforming to the Sequence Protocol

  • Conform to Sequence, IteratorProtocol protocol
  • implement next() -> Node<Value>? method
  • Note in next method we mutate head value and still after for in loop head reset
Figure 16
Figure 17
Figure 18

Conforming to the Collection Protocol

  • The startIndex and endIndex properties
  • A subscript that provides at least read-only access to your type’s elements
  • The index(after:) method for advancing an index into your collection

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Ali Akhtar

Ali Akhtar

Senior iOS Engineer | HungerStation | Delivery Hero