Swift data structures with examples. Part one: linked list

Foreword

Which of the iOS developers did not dream of working in a prestigious place like Yandex or Avito. Unfortunately, only hr asks about dreams at interviews, but developer interviewers ask questions of a slightly different nature. What is the difference between reference type and value type or bounds from frame? Questions that each of us has heard more than once at interviews. If your interview begins with the question about the differences between the significant and the reference types or in the spirit of “tell us about SOLID”, then you are clearly on the path to finding a job at So-so-Perspectives LLC.



In a decent company you will not be asked such nonsense. Get ready for questions about dispatching, side table and underlying queue. Knowing such nuances in no way will help to achieve 60 FPS when scrolling, loaded with cell elements and will not make you an honorary developer of Russia. They will help you recognize a person who has not just changed the xib-rate for 4 years and now considers himself a Senior iOS Developer, but is really interested in the platform. It will always remain a mystery to me at what point a person decides that he has reached the level of Middle or Senior. Probably participates in all-Russian competitions, in which ROS-GOS-iOS awards categories and ranks for fulfilling standards and prizes.



Back to the interviews. Not only will the prestigious employer ask tricky questions about the platform, but he will certainly ask about architecture. Wait for the question: “Why did you use VIPER and not MVVM in the last place?”. You may be asked: “What is bad MVC?“. Well, the last nail in the lid of the coffin will be algorithms. Even if you are brilliantly versed in iOS and the architecture of mobile applications, but don’t know the weaknesses of arrays and cannot optimize the search for an element, then after the interview, wait for an email reply:





On the expanses of the Russian-language Internet is full of articles about algorithms and data structures. The only drawback that can obscure the study is the scarcity of examples and implementations on Swift. It’s hard enough to understand this topic when you get a lot of obscure words and even more obscure C ++ examples.



For everyone who wants to drink smoothies every day in chic offices and at alumni meetings to talk about how he alone drags all of Sber’s mobile development, I prepared a couple of articles on data structures. Articles are intended for developers who are already familiar with generics, have worked with arrays / sets / dictionaries, understand the differences between classes and structures and pretend that they understand recursion. I will not paint the theory. This has already been done before me and I am sure that it is quite informative. Let's focus on the examples.

Linked list

Wikipedia will help with the theory . Let's start by creating the same node.





_{* Be sure to change your Xcode color scheme to dark otherwise you will not see work in Mail}



An attentive reader should ask the question: “Why did the Mamkin developer decide to implement the node as a class, not a structure? The article is about data structures! ” I suggest discussing this decision in the comments. Let's move on to the most linked list. The initial implementation will look like this:







Every self-respecting bore expert will note that WeakReference is some unknown type and will justifiably require implementation.







Add to the implementation methods responsible for filling our list:









_{* Complexity O (1) is valid only if there is no need to copy the structure. Otherwise, we will have O (n) complexity. This applies to all mutating methods.}



Add the methods responsible for removing from the list:









_{* @ discardableResult will save us from having to write "_ =" before calling the function when the return value is not interesting to us}



Our craft already looks like a working linked list. Let's try to make it as Swift-oriented as possible. To do this, we only need to implement two things: the BidirectionalCollection protocol and the copy-on-write technique. Let's start with the protocol. There are very few methods in it, and the most difficult thing is to understand and implement Index.









Wonderful! Now all our collection collections are available to our list. We can apply map, compactMap, filter, contains, etc. to it. Now it's the turn of copy-on-write. We implement the copyIfNeeded () method due to the lack of which the compiler is now hinting at that the code was not written by D'Artagnan:







Those who wish to ask a clever question or point out flaws are waiting in the comments.

PS I thank ivlevAstef for help in fixing the bugs. No one has yet proposed a working implementation without weak wrappers.



Github Code