DS & Algorithm (Linked List)

Linked List

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:

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

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

Figure 3

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 inoX12 address in memory

Figure 4

push operations

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

Figure 5

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 CustomStringConvertible protocol.

The description is required by the protocol and the string we compose in it will be printed in the console when using print() statement

append operations

“ This is meant to add a value at the end of the list, and it is known as tail-end insertion.”

Like before,

• 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:)

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

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

This operation inserts a value at a particular place in the list, and requires two steps:

1. Finding a particular node in the list.
2. Inserting the new node

As shown in Figure 7 if we need to insert 3 after 2 we need to first find 2 and 2 → next will be inserted item and inserted item will be will point to previous 2 → next item

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

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.

pop operations

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

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

Removing the last node of the list

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

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.

Figure 13

Performance analysis

You’ve hit another checkpoint! To recap, you’ve implemented the three operations that remove values from a linked list:

Figure 14

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

Figure 15

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 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

the example below we used the array’s contains(_:) method, which every sequence inherits from Sequence, instead of iterating manually:

Figure 17

What if we want to access linked list using subscript notation for that we need to conform to Collection protocol

Figure 18

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:

• 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

(In progress …………….. Just published beacuse this blog need this blog info )