Treehouse Intermediate Course - Part 6 (Generics 4)
So it's been a few days! But I'm back for more generics! Before I begin, I'm just going to recap what I've been looking at most recently.
Start Time - 20:32
OK so before it was the general info about generics, including the use of protocols and multiple parameters. Most recently, it was about generic types in the standard library. This was basically about what is in the swift documentation and how actual quite a few of the types are generics! So a dictionary shows generics in the sense that, once defined, it has specific types that must be conformed too. Going to skim over a bit more... Yes, some was on other ways to create arrays, optionals and also what's 'under the hood' for various bits. Generic types are used all the time including for custom data structures. OK, let's move on!
Linked Lists
Array - ordered set of data etc. etc.
A linked list - a set of data items that are connected to one another.
Each item is a NODE.
Two types - singly linked lists and doubly linked lists.
So we want all the class below went all the items to contain the same type of data.
class LinkedListNode<Key> {
In this we have a doubly linked list - the link ListNode and the previous. The previous has the weak keyword as we don't want a reference. Not sure about all this at the moment.
This is all pretty confusing. So I'm going to read up some more!
Extra Reading
https://www.raywenderlich.com/947-swift-algorithm-club-swift-linked-list-data-structure
So the two main types of linked lists are single linked lists -
And double linked lists -
The key thing is about references. In single link, each node has a reference to the NEXT node. In double, each has a reference to PREVIOUS and NEXT!
Also, there is HEAD and TAIL for where the list begins and ends.
So a similar example to Pasan's. No use of generics this time. You can use any data type for the value - it could be a custom data type like <Key> or whatever else. The next and previous are used as before.
So each node needs a pointer to the next class hence the use of the next value. It is OPTIONAL so doesn't need initializing. The last node in the list doesn't need a pointer in a single linked list.
Previous has been put in for the double linked list. So previous has been created. The WEAK is to do with ownership cycle. I've seen the use of this keyword before with labels in apps. It's about breaking the cycle to ensure deleted nodes stay deleted! THat's all I know for now...
The rest seems more confusing, so back to Treehouse to find out more for this next bit!
Linked List Operations
Wow - this is the code now for the node...
Start Time - 20:32
OK so before it was the general info about generics, including the use of protocols and multiple parameters. Most recently, it was about generic types in the standard library. This was basically about what is in the swift documentation and how actual quite a few of the types are generics! So a dictionary shows generics in the sense that, once defined, it has specific types that must be conformed too. Going to skim over a bit more... Yes, some was on other ways to create arrays, optionals and also what's 'under the hood' for various bits. Generic types are used all the time including for custom data structures. OK, let's move on!
Linked Lists
Array - ordered set of data etc. etc.
A linked list - a set of data items that are connected to one another.
Each item is a NODE.
Two types - singly linked lists and doubly linked lists.
So we want all the class below went all the items to contain the same type of data.
class LinkedListNode<Key> {
let key: Key
}
Right here it the completed node example -
class LinkedListNode<Key> {
let key: Key
var next: LinkedListNode?
weak var previous: LinkedListNode?
init(key: Key) {
self.key = key
}
}
In this we have a doubly linked list - the link ListNode and the previous. The previous has the weak keyword as we don't want a reference. Not sure about all this at the moment.
class LinkedList<Element> {
typealias Node = LinkedListNode<Element>
private var head: Node?
var first: Node? {
return head
}
var last: Node? {
if var node = head {
while node.next != nil {
node = node.next!
}
return node
} else {
return nil
}
}
This is all pretty confusing. So I'm going to read up some more!
Extra Reading
https://www.raywenderlich.com/947-swift-algorithm-club-swift-linked-list-data-structure
So the two main types of linked lists are single linked lists -
And double linked lists -
The key thing is about references. In single link, each node has a reference to the NEXT node. In double, each has a reference to PREVIOUS and NEXT!
Also, there is HEAD and TAIL for where the list begins and ends.
public class Node {
var value: String
init(value: String) {
self.value = value
}
var next: Node?
weak var previous: Node?
}
So a similar example to Pasan's. No use of generics this time. You can use any data type for the value - it could be a custom data type like <Key> or whatever else. The next and previous are used as before.
So each node needs a pointer to the next class hence the use of the next value. It is OPTIONAL so doesn't need initializing. The last node in the list doesn't need a pointer in a single linked list.
Previous has been put in for the double linked list. So previous has been created. The WEAK is to do with ownership cycle. I've seen the use of this keyword before with labels in apps. It's about breaking the cycle to ensure deleted nodes stay deleted! THat's all I know for now...
The rest seems more confusing, so back to Treehouse to find out more for this next bit!
Linked List Operations
Wow - this is the code now for the node...
class LinkedList<Element> {
typealias Node = LinkedListNode<Element>
private var head: Node?
var first: Node? {
return head
}
var last: Node? {
if var node = head {
while node.next != nil {
node = node.next!
}
return node
} else {
return nil
}
}
func append(_ value: Element) {
let new = Node(key: value)
if let lastNode = last {
lastNode.next = new
new.previous = lastNode
} else {
head = new
}
}
func node(atIndex index: Int) -> Node {
var node = head
var counter = 0
while node != nil {
if counter == index {
return node!
}
counter += 1
node = node?.next
}
fatalError("Index out of bounds")
}
func insert(_ value: Element, at index: Int) {
let nodeAtIndex = node(atIndex: index)
let nodeBeforeIndex = nodeAtIndex.previous
let new = Node(key: value)
new.previous = nodeBeforeIndex
new.next = nodeAtIndex
nodeAtIndex.previous = new
nodeBeforeIndex?.previous = new
if nodeBeforeIndex == nil {
head = new
}
}
}
Mental eh!!
I'm accepting that I am struggling with linked lists but am cracking on with it.
Now actually building the list -
let linkedList = LinkedList<String>()
linkedList.append("Jessica")
linkedList.append("Jennifer")
linkedList.append("Julia")
linkedList.insert("Jathu", at: 1)
It returns an array in terms of the items.
A neat trick -
class LinkedIntegers: LinkedList<Int> { }
let newList = LinkedIntegers()
newList.append(4)
The type is put in as the <Int> so for an instance of this, no need to specify the type!
Tough stuff!
So here we go - challenge time!
Let's give it a go...
struct Queue<Element> {
var array: [Element] = []
}
Cool!
struct Queue<Element> {
var array: [Element] = []
var isEmpty: Bool {
if array.count == 0 {
return true
} else {
return false
}
}
}
Needed a little help but wasn't far off!
var count: Int {
return array.count
}
Easy!
mutating func enqueue(_ element: Element) {
array.append(element)
}
So I needed some help - didn't even think of the keyword mutating!
mutating func dequeue() -> Element? {
var first: Element?
if isEmpty == false {
first = array.first
array.remove(at: 0)
return first
} else {
return first
}
}
Bloody hell, that was hard! A good thing has come up for the return part though. Anything after that return line won't be executed. SO that has to happen last!
The whole linked lists thing is pretty mental to be honest, but I've spent good time on it today and it's starting to make some sense.
Finish Time - 22:04 (1 hour 32 minutes!)
A long time to spend on something I'm still unsure about. But it's all necessary. Good experience and all. Tomorrow it will be to do with protocols so hopefully that will be useful. Looking ahead, it will be closures next! This will be exactly what I need to crack on with. So that's coming up soon! I'm sticking with Treehouse until at least the end of 'Intermediate' basically.
Comments
Post a Comment