data structure: Singly Linked List

Programming Languages Swift
g_dot_one OP
Created Jul ’20
Replies 15
Boosts 0
Views 3.7k
Participants 2
I'm trying to understand optionals and traversing the list. the code is not complete here. I stopped where I am puzzled. I will continue to flesh out the code, asking questions along the way.
thanks everyone. my question is at the bottom.

/* singly linked list */

import Foundation

public class Node {

    var value : String
    var next: Node?

   init(value:String) {
self.value = value
}

} // class Node

/********** linked list class *************/

public class LinkedList {

    var head: Node?
    var tail: Node?

   public var isEmpty: Bool {
return head == nil
}

   public var first: Node? {
return head
}
Code Block 
public var last: Node? {
		return tail
}

    public func append(value: String) {
let newNode = Node(value: value)
Code Block 
		if isEmpty {
            head = newNode
            let theValue = head?.value
            print(theValue!)
        }
}// end public func append(...)

}



/* driver so far */        

let l = LinkedList()
l.append(value: "asdf")


/****************
my question is about the print(theValue!) statement. why must the ! be uses? why could I not use let theValue = head?.value . or, why not let theValue = head?.head!**

  • *****************/

Replies  15
Boosts  0
Views  3.7k
Participants  2
OOPer OP
Jul ’20
Please enclose Code block with lines containing only ``` , that will make the styles better for reading as Code. Or the button with icon < > would help you doing so.

why must the ! be uses? why could I not use let theValue = head?.value .

Sorry, I do not understand this part. Can you tell us what you want to ask with other words or showing some example what it should be?

why not let theValue = head?.head!

Do you mean something like this?

Code Block 
            let theValue = head?.value!
            print(theValue)


It does not compile, because value is not Optional.
The expression head?.value is Optional, but Swift parser applies ! to value, not head?.value in Optional chaining of Swift.
You can write something like this instead.
Code Block 
						let theValue = (head?.value)!
						print(theValue)

But when you eventually need to use forced-unwrapping (!), I would do it as soon as possible.
Code Block 
						let theValue = head!.value
						print(theValue)

But, as you know, theValue is always the same as value there. I do not understand why head!.value is used, some sort of debugging need?
0
g_dot_one OP
Jul ’20 
Code Block import Foundation
public class Node
{
    var value : String
    var next: Node?
    
    
    init(value:String){
        self.value = value
    }
}
public class LinkedList {
    var head: Node?
    var tail: Node?
    
    
    public var isEmpty: Bool {
        return head == nil
    }
    
    public var first: Node? {
        return head
    }
    public var last: Node? {
        return tail
    }
    
    public func append(value: String) {
        let newNode = Node(value: value)
        
        if isEmpty {
            head = newNode
            
        }
        else
        {
            var current: Node?
            current = head
            while current?.next != nil {
                current = current?.next
                if current?.next == nil{
                    break
                }
                current?.next = newNode
            }
            
        }
        
    }// end public func append(...)
    
    public func printList(){
        var current: Node?
        current = head
        
        while current?.next != nil {
            current = current?.next
            // let theValue = current?.next
            print(current!.value)
            if current?.next == nil {
                break
            }
            print(current!.value)
        }
    } // end func printList()
    
    
}
        
let l = LinkedList()
l.append(value: "asdf")
l.append(value: "zxcv")
l.printList()

why does this not work?
0
OOPer OP
Jul ’20

why does this not work? 

I do not know why you do not use tail, but if you expect two methods, append and printList, to work as a usual list operation, you may need to modify them a little bit.
Code Block 
		public func append(value: String) {
				let newNode = Node(value: value)
				
				if isEmpty {
						head = newNode
				} else {
						//Search for the last Node...
						var current: Node?
						current = head
						while current?.next != nil {
								//Another check for `nil` is not needed
								current = current?.next
						}
						current?.next = newNode //<-Get this out of `while`
				}
		}
		
		public func printList() {
				var current: Node?
				current = head
				
				//Start loop from `current`
				while current != nil { //Check `current`, not `current?.next`
						print(current!.value)
						//Another check for `nil` is not needed
						current = current?.next
				}
		}


0
g_dot_one OP
Jul ’20 
Code Block import Foundation
public class Node
{
    var value : String
    var next: Node?   
    init(value:String){
        self.value = value
    }
}
public class LinkedList {
    var head: Node?
    var tail: Node?    
    public var isEmpty: Bool {
        return head == nil
    }
    public var first: Node? {
        return head
    }
    public var last: Node? {
        return tail
    }
    public func append(value: String)
    {
        let newNode = Node(value: value)
       
        if isEmpty
        {
            head = newNode
        }
        else
        {
            var current: Node?
            current = head
            while current?.next != nil
            {
                current = current?.next
            }
        } // end else
        tail = newNode
    }// end public func append(...)
    public func printList()
    {
        var current: Node?
        current = head
        while current != nil 
				{
            print(current!.value)
            current = current?.next
        } // end while current ...
    } // end func printList()   
} // end class LinkedList
     
let l = LinkedList()
l.append(value: "asdf")
l.append(value: "zxcv")
l.append(value: "thru")
l.printList()

I'm missing something. if the list is empty then create a node and have head point to it. head will not be moved. if the in something in the list, move to the last node, my thought was move to what the last pointer in the list points to. now have that pointer point to a newNode. have tail point to that node. I don't think that is what is happening as I view the code in playground. and print the list is not happening at all.
0
OOPer OP
Jul ’20
As a good manner, you should better reply to answers before writing something new. Answerers are spending their time to help you.
Ignoring them is sort of rude.
0
g_dot_one OP
Jul ’20
what did I not answer?

0
g_dot_one OP
Jul ’20
what are your questions?

0
OOPer OP
Jul ’20

what did I not answer?

I am not saying you did not answer. I said you have not replied to answers to your questions.
Something like "that worked" would be enough.

what are your questions?

No questions. Just telling you the better way to communicate with other developers watching the forums.
0
g_dot_one OP
Jul ’20
oh ok.
0
g_dot_one OP
Jul ’20
it was great help. needed to think through what you told me. the code below works.
will use tail so not to have to traverse the list each time to add a node at the end.

Code Block import Foundation
public class Node
{
		var value : String
		var next: Node?
		
		
		init(value:String){
				self.value = value
		}
}
public class LinkedList {
		var head: Node?
		var tail: Node?
		
		
		public var isEmpty: Bool {
				return head == nil
		}
		
		public var first: Node? {
				return head
		}
		public var last: Node? {
				return tail
		}
		
		public func append(value: String)
		{
				let newNode = Node(value: value)
				
				if isEmpty
				{
						head = newNode
						
				}
				else
				{
						var current: Node?
						current = head
						while current?.next != nil
						{
								current = current?.next
						}
						
						current?.next = newNode		// this addition makes sense to me
						
				} // end else
						
				tail = newNode								// really don't need tail, but it would
																			// come in handy. could save the traversal
																			// through the loop each time to find the 
																			// end
		}// end public func append(...)
		
		
		public func printList()
		{
				var current: Node?
				current = head
				
				while current != nil {
						print(current!.value)
						current = current?.next
						
				} // end while current ...
				
		} // end func printList()
		
		
} // end class LinkedList
				
let l = LinkedList()
l.append(value: "asdf")
l.append(value: "zxcv")
l.append(value: "thru")
l.printList()


thanks for the help. :-) don't go far, doubly is next, then circular, then trees.
will add a view more functions to linked list. understanding when to unwrap
and how to, forced...
thanks again.
0
OOPer OP
Jul ’20
Ok, it seems your next step is utilizing tail.
It is a well-known technic to accelerate append.

The while-loop is not needed when you utilize tail.

Please try something like this.
Code Block 
		public func append(value: String) {
				let newNode = Node(value: value)
				
				if isEmpty {
						head = newNode
				} else {
						//Add `newNode` next to the old `tail`
						tail?.next = newNode
				}
				tail = newNode
		}


0
g_dot_one OP
Jul ’20
Ah, yes! that makes sense. very good, excellent. yes tail does keep
moving so to speak. it always points at the last node. so assigning
tail?.next will point to the new node. nice.
0
g_dot_one OP
Jul ’20
I have a general question, what are extensions used for? and why
use an extensions?
0
OOPer OP
Jul ’20

what are extensions used for? and why use an extensions?

This is a bit too far from implementing single-linked list, so just shortly.

In Swift, extensions are used mainly for two purposes.

  • Adding functionalities or conformance to protocols to existing types

  • Bind implementations of methods or properties into separate groups to improve readability

If you want to see more detailed explanations or concrete examples, I recommend you to start a new thread focusing this topic.
(Though there were similar questions already, but) With starting a new thread you will get more chances to get replies from more people.
0
g_dot_one OP
Jul ’20
ok, thanks
0
data structure: Singly Linked List
First post date Last post date
 
 
Q