June 12, 2019 at 15:23Spread a singly linked list. Swift edition
It's no secret that one of the favorite pastimes for a software developer is interviewing employers. We all do this from time to time and for completely different reasons. And the most obvious of them - job search - I think, is not the most common. Attending an interview is a good way to keep fit, repeat forgotten basics, and learn something new. And if successful, also increase self-confidence. We get bored, we set ourselves the status “open for offers” on some kind of “business” social network like “LinkedIn” - and the army of human resource managers is already attacking our inboxes for incoming messages.
In the process, while all this bedlam is going on, we are faced with many questions that, as they say on the other side of the implicitly collapsed curtain, are “ring a bell”, and their details are hidden behind the fog of war . They are most often recalled only on tests by algorithms and data structures (personally, I didn’t have such data at all) and actually interviews.
One of the most common questions in an interview for a programmer of any specialization is lists. For example, singly linked lists. And related basic algorithms. For example, a U-turn. And usually this happens somehow like this: “Good, but how would you expand a singly linked list?” The main thing is to catch the applicant by surprise with this question.
Actually, all this led me to write this short review for constant reminder and edification. So, jokes aside, behold!
A linked list is one of the basic data structures . Each element (or node) of it consists of, in fact, stored data and links to neighboring elements. A singly linked list only stores a link to the next element in the structure, and a doubly linked list holds the link to the next and previous. Such organization of data allows them to be located in any memory area (unlike, for example, an array , all of whose elements should be located in memory one after another).
There is much more to be said about lists, of course: they can be circular (i.e., the last element stores a link to the first) or not (i.e. there is no link to the last element). Lists can be typed, i.e. contain data of the same type or not. And so on and so forth.
Better try writing some code. For example, somehow you can imagine a list node:
“Generic” is a type that
The list itself is exhaustively identified by its first node:
The first node is declared optional, because the list may well be empty.
In theory, of course, in the class you need to implement all the necessary methods - insert, delete, access to nodes, etc., but we will do it some other time. At the same time, we will check whether using
It's time to get down to business for which we are here today! And the most effective way to deal with it is two ways. The first is a simple loop, from the first to the last node.
The cycle works with three variables, which before the beginning are assigned the value of the previous, current and next node. (At this moment, the value of the previous node is naturally empty.) The cycle begins by checking that the next node is not empty, and if so, the body of the cycle is executed. No magic happens in the loop: at the current node, the field that refers to the next element is assigned a link to the previous one (at the first iteration, the value of the link, respectively, is reset, which corresponds to the state of affairs in the last node). Well and further the variables corresponding to the previous, current and next node are assigned new values. After exiting the loop, the current (i.e., the last iterable in general) node is assigned a new link value to the next node, because the exit from the cycle occurs just at the moment
In words, of course, all this sounds strange and incomprehensible, so it’s better to look at the code:
For verification, we use a list of nodes whose payloads are simple integer identifiers. Create a list of ten elements:
Everything seems to be fine, but we are people, not computers, and it would be nice for us to get a visual proof of the correctness of the created list and the algorithm described above. Perhaps a simple print will be enough. To make the conclusion readable, we add protocol implementations to the
... And the corresponding list to display all the nodes in order:
The string representation of our types will contain an address in memory and an integer identifier. Using them, we organize the printing of the generated list of ten nodes:
Expand this list and print it again:
You may notice that the addresses in the memory of the list and nodes have not changed, and the nodes of the list are printed in the reverse order. Links to the next element of the node now point to the previous one (that is, for example, the next element of the node “5” is now not “6”, but “4”). And that means we did it!
The second known way to do the same U-turn is based on recursion . To implement it, we will declare a function that takes the first node of the list, and returns the “new” first node (which was the last before).
The parameter and return value are optional, because inside this function it is called again and again on each subsequent node until it is empty (i.e. until the end of the list is reached). Accordingly, in the body of the function, it is necessary to check whether the node on which the function is called is empty and whether this node has the following. If not, then the function returns what was passed to the argument.
Actually, I honestly tried to describe the complete algorithm in words, but in the end I erased almost everything, because the result would be impossible to understand. To draw flowcharts and formally describe the steps of the algorithm - also, in this case, I think it makes no sense, because it will be more convenient for you and me to just read and try to comprehend the Swift code :
The algorithm itself is “wrapped” by a method of the type of the actual list, for the convenience of calling.
It looks shorter, but, in my opinion, harder to understand.
We call this method on the result of the previous spread and print a new result:
It can be seen from the output that all addresses in the memory have not changed again, and the nodes now follow in the original order (that is, they are “deployed” again). And that means we got it right again!
If you look at the reversal methods carefully (or conduct an experiment with call counting), you will notice that the loop in the first case and the internal (recursive) method call in the second case occur one time less than the number of nodes in the list (in our case, nine time). You can also pay attention to what happens around the loop in the first case - the same sequence of assignments - and to the first, non-recursive, method call in the second case. It turns out that in both cases the “circle” is repeated exactly ten times for a list of ten nodes. Thus, we have linear complexity for both algorithms - O (n) .
Generally speaking, the two algorithms described are considered the most effective for solving this problem. As for computational complexity, it’s not possible to come up with an algorithm with a lower value: one way or another, you need to “visit” each node to assign a new value to the one stored inside the link.
Another feature worth mentioning is “allocated memory complexity”. Both proposed algorithms create a fixed number of new variables (three in the first case and one in the second). This means that the amount of allocated memory does not depend on the quantitative characteristics of the input data and is described by a constant function - O (1).
But, in fact, in the second case this is not so. The danger of recursion is that for every recursive call on the stackadditional memory is allocated. In our case, the recursion depth corresponds to the amount of input data.
And finally, I decided to experiment a little more: in a simple and primitive way I measured the absolute execution time of two methods for a different amount of input data. Like this:
And here’s what I got (this is the “raw” data from the “Playground” ):
(Unfortunately, my computer has not mastered the larger values.)
What can I see from the table? Nothing special yet. Although it is already noticeable that the recursive method behaves a little worse with a relatively small number of nodes, but somewhere between 100 and 1000 it starts to show better.
I also tried the same simple test inside a full-fledged “Xcode” project. The results were as follows:
First, it is worth mentioning that the results were obtained after activating the "aggressive" optimization mode, aimed at execution speed (
I tried to cover a rather classic topic from the point of view of my favorite programming language at the moment, and I hope you were curious to follow the progress as well as myself. I’m also very glad if you managed to learn something new as well - then I definitely wasted my time in this article (instead of sitting and watching TV shows ).
If someone has a desire to track my social activity, here is a link to my “Twitter” , where first of all there are links to my new posts and a little more.
In the process, while all this bedlam is going on, we are faced with many questions that, as they say on the other side of the implicitly collapsed curtain, are “ring a bell”, and their details are hidden behind the fog of war . They are most often recalled only on tests by algorithms and data structures (personally, I didn’t have such data at all) and actually interviews.
One of the most common questions in an interview for a programmer of any specialization is lists. For example, singly linked lists. And related basic algorithms. For example, a U-turn. And usually this happens somehow like this: “Good, but how would you expand a singly linked list?” The main thing is to catch the applicant by surprise with this question.
Actually, all this led me to write this short review for constant reminder and edification. So, jokes aside, behold!
Singly linked list
A linked list is one of the basic data structures . Each element (or node) of it consists of, in fact, stored data and links to neighboring elements. A singly linked list only stores a link to the next element in the structure, and a doubly linked list holds the link to the next and previous. Such organization of data allows them to be located in any memory area (unlike, for example, an array , all of whose elements should be located in memory one after another).
There is much more to be said about lists, of course: they can be circular (i.e., the last element stores a link to the first) or not (i.e. there is no link to the last element). Lists can be typed, i.e. contain data of the same type or not. And so on and so forth.
Better try writing some code. For example, somehow you can imagine a list node:
final class Node {
let payload: T
var nextNode: Node?
init(payload: T, nextNode: Node? = nil) {
self.payload = payload
self.nextNode = nextNode
}
}
“Generic” is a type that
payloadcan store any kind of payload in a field . The list itself is exhaustively identified by its first node:
final class SinglyLinkedList {
var firstNode: Node?
init(firstNode: Node? = nil) {
self.firstNode = firstNode
}
}
The first node is declared optional, because the list may well be empty.
In theory, of course, in the class you need to implement all the necessary methods - insert, delete, access to nodes, etc., but we will do it some other time. At the same time, we will check whether using
struct(which Apple actively encourages us with our example) is a better choice, and perhaps recall the “Copy-on-write” approach.Single-linked list spread
The first way. Cycle
It's time to get down to business for which we are here today! And the most effective way to deal with it is two ways. The first is a simple loop, from the first to the last node.
The cycle works with three variables, which before the beginning are assigned the value of the previous, current and next node. (At this moment, the value of the previous node is naturally empty.) The cycle begins by checking that the next node is not empty, and if so, the body of the cycle is executed. No magic happens in the loop: at the current node, the field that refers to the next element is assigned a link to the previous one (at the first iteration, the value of the link, respectively, is reset, which corresponds to the state of affairs in the last node). Well and further the variables corresponding to the previous, current and next node are assigned new values. After exiting the loop, the current (i.e., the last iterable in general) node is assigned a new link value to the next node, because the exit from the cycle occurs just at the moment
In words, of course, all this sounds strange and incomprehensible, so it’s better to look at the code:
extension SinglyLinkedList {
func reverse() {
var previousNode: Node? = nil
var currentNode = firstNode
var nextNode = firstNode?.nextNode
while nextNode != nil {
currentNode?.nextNode = previousNode
previousNode = currentNode
currentNode = nextNode
nextNode = currentNode?.nextNode
}
currentNode?.nextNode = previousNode
firstNode = currentNode
}
}
For verification, we use a list of nodes whose payloads are simple integer identifiers. Create a list of ten elements:
let node = Node(payload: 0) // T == Int
let list = SinglyLinkedList(firstNode: node)
var currentNode = node
var nextNode: Node
for id in 1..<10 {
nextNode = Node(payload: id)
currentNode.nextNode = nextNode
currentNode = nextNode
}
Everything seems to be fine, but we are people, not computers, and it would be nice for us to get a visual proof of the correctness of the created list and the algorithm described above. Perhaps a simple print will be enough. To make the conclusion readable, we add protocol implementations to the
CustomStringConvertiblenode with an integer identifier:extension Node: CustomStringConvertible where T == Int {
var description: String {
let firstPart = """
Node \(Unmanaged.passUnretained(self).toOpaque()) has id \(payload) and
"""
if let nextNode = nextNode {
return firstPart + " next node \(nextNode.payload)."
} else {
return firstPart + " no next node."
}
}
}
... And the corresponding list to display all the nodes in order:
extension SinglyLinkedList: CustomStringConvertible where T == Int {
var description: String {
var description = """
List \(Unmanaged.passUnretained(self).toOpaque())
"""
if firstNode != nil {
description += " has nodes:\n"
var node = firstNode
while node != nil {
description += (node!.description + "\n")
node = node!.nextNode
}
return description
} else {
return description + " has no nodes."
}
}
}
The string representation of our types will contain an address in memory and an integer identifier. Using them, we organize the printing of the generated list of ten nodes:
print(String(describing: list))
/*
List 0x00006000012e1a60 has nodes:
Node 0x00006000012e2380 has id 0 and next node 1.
Node 0x00006000012e8d40 has id 1 and next node 2.
Node 0x00006000012e8d20 has id 2 and next node 3.
Node 0x00006000012e8ce0 has id 3 and next node 4.
Node 0x00006000012e8ae0 has id 4 and next node 5.
Node 0x00006000012e89a0 has id 5 and next node 6.
Node 0x00006000012e8900 has id 6 and next node 7.
Node 0x00006000012e8a40 has id 7 and next node 8.
Node 0x00006000012e8a60 has id 8 and next node 9.
Node 0x00006000012e8820 has id 9 and no next node.
*/
Expand this list and print it again:
list.reverse()
print(String(describing: list))
/*
List 0x00006000012e1a60 has nodes:
Node 0x00006000012e8820 has id 9 and next node 8.
Node 0x00006000012e8a60 has id 8 and next node 7.
Node 0x00006000012e8a40 has id 7 and next node 6.
Node 0x00006000012e8900 has id 6 and next node 5.
Node 0x00006000012e89a0 has id 5 and next node 4.
Node 0x00006000012e8ae0 has id 4 and next node 3.
Node 0x00006000012e8ce0 has id 3 and next node 2.
Node 0x00006000012e8d20 has id 2 and next node 1.
Node 0x00006000012e8d40 has id 1 and next node 0.
Node 0x00006000012e2380 has id 0 and no next node.
*/
You may notice that the addresses in the memory of the list and nodes have not changed, and the nodes of the list are printed in the reverse order. Links to the next element of the node now point to the previous one (that is, for example, the next element of the node “5” is now not “6”, but “4”). And that means we did it!
The second way. Recursion
The second known way to do the same U-turn is based on recursion . To implement it, we will declare a function that takes the first node of the list, and returns the “new” first node (which was the last before).
The parameter and return value are optional, because inside this function it is called again and again on each subsequent node until it is empty (i.e. until the end of the list is reached). Accordingly, in the body of the function, it is necessary to check whether the node on which the function is called is empty and whether this node has the following. If not, then the function returns what was passed to the argument.
Actually, I honestly tried to describe the complete algorithm in words, but in the end I erased almost everything, because the result would be impossible to understand. To draw flowcharts and formally describe the steps of the algorithm - also, in this case, I think it makes no sense, because it will be more convenient for you and me to just read and try to comprehend the Swift code :
extension SinglyLinkedList {
func reverseRecursively() {
func reverse(_ node: Node?) -> Node? {
guard let head = node else { return node }
if head.nextNode == nil { return head }
let reversedHead = reverse(head.nextNode)
head.nextNode?.nextNode = head
head.nextNode = nil
return reversedHead
}
firstNode = reverse(firstNode)
}
}
The algorithm itself is “wrapped” by a method of the type of the actual list, for the convenience of calling.
It looks shorter, but, in my opinion, harder to understand.
We call this method on the result of the previous spread and print a new result:
list.reverseRecursively()
print(String(describing: list))
/*
List 0x00006000012e1a60 has nodes:
Node 0x00006000012e2380 has id 0 and next node 1.
Node 0x00006000012e8d40 has id 1 and next node 2.
Node 0x00006000012e8d20 has id 2 and next node 3.
Node 0x00006000012e8ce0 has id 3 and next node 4.
Node 0x00006000012e8ae0 has id 4 and next node 5.
Node 0x00006000012e89a0 has id 5 and next node 6.
Node 0x00006000012e8900 has id 6 and next node 7.
Node 0x00006000012e8a40 has id 7 and next node 8.
Node 0x00006000012e8a60 has id 8 and next node 9.
Node 0x00006000012e8820 has id 9 and no next node.
*/
It can be seen from the output that all addresses in the memory have not changed again, and the nodes now follow in the original order (that is, they are “deployed” again). And that means we got it right again!
conclusions
If you look at the reversal methods carefully (or conduct an experiment with call counting), you will notice that the loop in the first case and the internal (recursive) method call in the second case occur one time less than the number of nodes in the list (in our case, nine time). You can also pay attention to what happens around the loop in the first case - the same sequence of assignments - and to the first, non-recursive, method call in the second case. It turns out that in both cases the “circle” is repeated exactly ten times for a list of ten nodes. Thus, we have linear complexity for both algorithms - O (n) .
Generally speaking, the two algorithms described are considered the most effective for solving this problem. As for computational complexity, it’s not possible to come up with an algorithm with a lower value: one way or another, you need to “visit” each node to assign a new value to the one stored inside the link.
Another feature worth mentioning is “allocated memory complexity”. Both proposed algorithms create a fixed number of new variables (three in the first case and one in the second). This means that the amount of allocated memory does not depend on the quantitative characteristics of the input data and is described by a constant function - O (1).
But, in fact, in the second case this is not so. The danger of recursion is that for every recursive call on the stackadditional memory is allocated. In our case, the recursion depth corresponds to the amount of input data.
And finally, I decided to experiment a little more: in a simple and primitive way I measured the absolute execution time of two methods for a different amount of input data. Like this:
let startDate = Date().timeIntervalSince1970
// list.reverse() / list.reverseRecursively()
let finishDate = Date().timeIntervalSince1970
let runningTime = finishDate – startDate // Seconds
And here’s what I got (this is the “raw” data from the “Playground” ):
(Unfortunately, my computer has not mastered the larger values.)
What can I see from the table? Nothing special yet. Although it is already noticeable that the recursive method behaves a little worse with a relatively small number of nodes, but somewhere between 100 and 1000 it starts to show better.
I also tried the same simple test inside a full-fledged “Xcode” project. The results were as follows:
First, it is worth mentioning that the results were obtained after activating the "aggressive" optimization mode, aimed at execution speed (
-Ofast), which is partly why the numbers are so small. It is also interesting that in this case the recursive method showed itself a little better, on the contrary, only on very small sizes of input data, and already on a list of 100 nodes, the method loses. Out of 100,000, he made the program terminate abnormally.Conclusion
I tried to cover a rather classic topic from the point of view of my favorite programming language at the moment, and I hope you were curious to follow the progress as well as myself. I’m also very glad if you managed to learn something new as well - then I definitely wasted my time in this article (instead of sitting and watching TV shows ).
If someone has a desire to track my social activity, here is a link to my “Twitter” , where first of all there are links to my new posts and a little more.