A linked list is a collection of values arranged in a linear unidirectional sequence. A linked list has several theoretical advantages over contiguous storage options such as the Swift Array:
- Constant time insertion and removal from the front of the list.
- Reliable performance characteristics.
As the diagram suggests, a linked list is a chain of nodes. Nodes have two responsibilities:
- Hold a value
- Hold a reference to the next node. A nil value represents the end of the list
As shown in Figure 3 this is the structure of Linked list ,
head holds the reference of first item in the list and
tail holds reference of last item in the list
As shown in Figure 4 memory structure of array and linked list and you can see if you have a reference of array you can access its element easily since it is stored contagious (meaning the second element of array is next to memory sequence) where as linked list element can be in any location, that’s why head hold the reference of first element which is
oX10 and that element holds the reference of next element which is in
oX12 address in memory
Adding a value at the front of the list is known as a push operation. This is also known as head-first insertion.
As shown in Figure 5 we did few things
- 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
if we wanted to get more info about the object being printed and, most importantly, in a human-readable way? For that, we have a great tool — the
description is required by the protocol and the string we compose in it will be printed in the console when using
“ This is meant to add a value at the end of the list, and it is known as tail-end insertion.”
- 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.
will try to retrieve a node in the list based on the given index. Since you can only access the nodes of the list from the head node, you’ll have to make iterative traversal
- You create a new reference to head and keep track of the current number of traversals.
- 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.
This operation inserts a value at a particular place in the list, and requires two steps:
- Finding a particular node in the list.
- Inserting the new node
As shown in Figure 7 if we need to insert
2 we need to first find
2 → next will be inserted item and inserted item will be will point to previous
2 → next item
- 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.
- Otherwise, you simply link up the new node with the rest of the list and return the new node.
Whew! You’ve made good progress so far. To recap, you’ve implemented the three operations that add values to a linked list and a method to find a node at a particular index.
Removing a value at the front of the list is often referred to as pop. This operation is almost as simple as push, so dive right in
- pop returns the value that was removed from the list. This value is optional, since it’s possible that the list is empty.
- By moving the head down a node, you’ve effectively removed the first node of the list.
- ARC will remove the old node from memory once the method finishes, since there will be no more references attached to it.
- In the event that the list becomes empty, you set tail to nil.
Removing the last node of the list
- If head is nil, there’s nothing to remove, so you return nil.
- 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.
- You keep searching for a next node until current.next is tail which means we reached to node 4
- Since current is the second last node we make this as tail and make next to nil which ARC auto free memory
The unlinking of the nodes occurs in the defer block. Special care needs to be taken if the removed node is the tail node, since the tail reference will need to be updated.
You’ve hit another checkpoint! To recap, you’ve implemented the three operations that remove values from a linked list:
Becoming a Swift collection
I want to use my Linked list as for in loop and when i do and swift compiler give me error
For-in loop requires ‘LinkedList<Int>’ to conform to ‘Sequence
Conforming to the Sequence Protocol
Making your own custom types conform to Sequence enables many useful operations, like for-in looping and the contains method, without much effort. To add Sequence conformance to your own custom type, add a makeIterator() method that returns an iterator.
Alternatively, if your type can act as its own iterator, implementing the requirements of the IteratorProtocol protocol and declaring conformance to both Sequence and IteratorProtocol are sufficient.
Here’s a definition of a Countdown sequence that serves as its own iterator. The makeIterator() method is provided as a default implementation.
As shown in Figure 16 we are using linked list items as for in loop , we just did few things
- Conform to
next() -> Node<Value>?method
- Note in next method we mutate head value and still after for in loop head reset
the example below we used the array’s
contains(_:) method, which every sequence inherits from
Sequence, instead of iterating manually:
What if we want to access linked list using subscript notation for that we need to conform to Collection protocol
Conforming to the Collection Protocol
If you create a custom sequence that can provide repeated access to its elements, make sure that its type conforms to the
Collection protocol in order to give a more useful and more efficient interface for sequence and collection operations. To add
Collection conformance to your type, you must declare at least the following requirements:
- A subscript that provides at least read-only access to your type’s elements
index(after:)method for advancing an index into your collection
(In progress …………….. Just published beacuse this blog need this blog info )