SHARE
TWEET

Untitled

a guest Oct 14th, 2019 91 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. //
  2. //  linkedlist.swift
  3. //  CommandLinePlayground
  4. //
  5. //  Created by Michael Rockhold on 9/24/19.
  6. //  Copyright © 2019 Michael Rockhold. All rights reserved.
  7. //
  8.  
  9. import Foundation
  10.  
  11. indirect enum LinkedList<Value: Comparable> {
  12.    
  13.     enum LinkedListError : Error {
  14.         case IndexOutOfRange
  15.     }
  16.    
  17.     case Empty
  18.     case List(LinkedList,Value)
  19.    
  20.     /** Initialize your data structure here. */
  21.     init() {
  22.         self = .Empty
  23.     }
  24.  
  25.     private func _length(offset: Int) -> Int {
  26.         if case let .List(next, _) = self {
  27.             // this list is not empty
  28.             return 1 + next._length(offset: offset+1)
  29.  
  30.         } else {
  31.             // this list is empty
  32.             return 0
  33.         }
  34.     }
  35.  
  36.     var length: Int {
  37.         return _length(offset: 0)
  38.     }
  39.    
  40.     /** Get the value of the index-th node in the linked list. If the index is invalid, return -1. */
  41.     func get(_ index: Int) throws -> Value {
  42.         return try _get(index, offset: 0)
  43.     }
  44.    
  45.     private func _get(_ index: Int, offset: Int) throws -> Value {
  46.        
  47.         if case let .List(next, value) = self {
  48.             // this list is not empty
  49.             return offset == index ? value : try next._get(index, offset: offset+1)
  50.  
  51.         } else {
  52.             // this list is empty, return an error value
  53.             throw LinkedListError.IndexOutOfRange
  54.         }
  55.     }
  56.    
  57.     /** Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list. */
  58.     mutating func addAtHead(_ val: Value) {
  59.        
  60.         if case .List(_, _) = self {
  61.             // this list is not empty; make self a new list that points to current self as 'next'
  62.             self = .List(self, val)
  63.  
  64.         } else {
  65.             // this list is empty
  66.             self = .List(.Empty, val)
  67.         }
  68.     }
  69.    
  70.     /** Append a node of value val to the last element of the linked list. */
  71.     mutating func addAtTail(_ val: Value) {
  72.        
  73.         if case var .List(next, value) = self {
  74.             // this list is not empty; append this new value to the 'next' list
  75.             next.addAtTail(val)
  76.             self = .List(next, value)
  77.  
  78.         } else {
  79.             // this list is empty
  80.             self = .List(.Empty, val)
  81.         }
  82.     }
  83.    
  84.     /** Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted. */
  85.     mutating func addAtIndex(_ index: Int, _ val: Value) {
  86.        
  87.         if case var .List(next, value) = self {
  88.             // this list is not empty
  89.             if index == 0 {
  90.                 addAtHead(val)
  91.             } else {
  92.                 next.addAtIndex(index-1, val)
  93.                 self = .List(next, value)
  94.             }
  95.  
  96.         } else {
  97.             // this list is empty; if the index == 0, add this value here
  98.             if index == 0 {
  99.                 self = .List(.Empty, val)
  100.             } else {
  101.                 // this should raise an error
  102.             }
  103.         }
  104.     }
  105.  
  106.     /** Delete the index-th node in the linked list, if the index is valid. */
  107.     mutating func deleteAtIndex(_ index: Int) {
  108.        
  109.         if case var .List(next, value) = self {
  110.             if index == 0 {
  111.                 self = next
  112.             } else {
  113.                 next.deleteAtIndex(index - 1)
  114.                 self = .List(next, value)
  115.             }
  116.         } else {
  117.             if index == 0 {
  118.                 self = .Empty
  119.             } else {
  120.                 // this should raise an error, as the index is too big for this list
  121.             }
  122.         }
  123.     }
  124. }
  125.  
  126. class MyLinkedList {
  127.  
  128.     private var implList = LinkedList<Int>()
  129.    
  130.     /** Get the value of the index-th node in the linked list. If the index is invalid, return -1. */
  131.     func get(_ index: Int) -> Int {
  132.         do {
  133.             return try implList.get(index)
  134.         } catch {
  135.             return -1
  136.         }
  137.     }
  138.    
  139.     /** Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list. */
  140.     func addAtHead(_ val: Int) {
  141.         implList.addAtHead(val)
  142.     }
  143.    
  144.     /** Append a node of value val to the last element of the linked list. */
  145.     func addAtTail(_ val: Int) {
  146.         implList.addAtTail(val)
  147.     }
  148.    
  149.     /** Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted. */
  150.     func addAtIndex(_ index: Int, _ val: Int) {
  151.         implList.addAtIndex(index, val)
  152.     }
  153.    
  154.     /** Delete the index-th node in the linked list, if the index is valid. */
  155.     func deleteAtIndex(_ index: Int) {
  156.         implList.deleteAtIndex(index)
  157.     }
  158. }
  159.  
  160.  
  161.  
  162.  
  163. func test_linkedlist() {
  164.        
  165.     var list = LinkedList<Int>()
  166.    
  167.     let ret_1: Int
  168.     do {
  169.         ret_1 = try list.get(0)
  170.     } catch {
  171.         ret_1 = -1
  172.     }
  173.    
  174.     print(ret_1 == -1)
  175.     print(list.length == 0)
  176.    
  177.     list.addAtHead(7)
  178.     do {
  179.         print(try list.get(0) == 7)
  180.     } catch {
  181.         print("false")
  182.     }
  183.     print(list.length == 1)
  184.  
  185.     list.addAtTail(5)
  186.     print(list.length == 2)
  187.    
  188.     list.addAtIndex(1, 3)
  189.     print(list.length == 3)
  190.    
  191.     list.deleteAtIndex(1)
  192.     print(list.length == 2)
  193. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top