Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //
- // linkedlist.swift
- // CommandLinePlayground
- //
- // Created by Michael Rockhold on 9/24/19.
- // Copyright © 2019 Michael Rockhold. All rights reserved.
- //
- import Foundation
- indirect enum LinkedList<Value: Comparable> {
- enum LinkedListError : Error {
- case IndexOutOfRange
- }
- case Empty
- case List(LinkedList,Value)
- /** Initialize your data structure here. */
- init() {
- self = .Empty
- }
- private func _length(offset: Int) -> Int {
- if case let .List(next, _) = self {
- // this list is not empty
- return 1 + next._length(offset: offset+1)
- } else {
- // this list is empty
- return 0
- }
- }
- var length: Int {
- return _length(offset: 0)
- }
- /** Get the value of the index-th node in the linked list. If the index is invalid, return -1. */
- func get(_ index: Int) throws -> Value {
- return try _get(index, offset: 0)
- }
- private func _get(_ index: Int, offset: Int) throws -> Value {
- if case let .List(next, value) = self {
- // this list is not empty
- return offset == index ? value : try next._get(index, offset: offset+1)
- } else {
- // this list is empty, return an error value
- throw LinkedListError.IndexOutOfRange
- }
- }
- /** 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. */
- mutating func addAtHead(_ val: Value) {
- if case .List(_, _) = self {
- // this list is not empty; make self a new list that points to current self as 'next'
- self = .List(self, val)
- } else {
- // this list is empty
- self = .List(.Empty, val)
- }
- }
- /** Append a node of value val to the last element of the linked list. */
- mutating func addAtTail(_ val: Value) {
- if case var .List(next, value) = self {
- // this list is not empty; append this new value to the 'next' list
- next.addAtTail(val)
- self = .List(next, value)
- } else {
- // this list is empty
- self = .List(.Empty, val)
- }
- }
- /** 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. */
- mutating func addAtIndex(_ index: Int, _ val: Value) {
- if case var .List(next, value) = self {
- // this list is not empty
- if index == 0 {
- addAtHead(val)
- } else {
- next.addAtIndex(index-1, val)
- self = .List(next, value)
- }
- } else {
- // this list is empty; if the index == 0, add this value here
- if index == 0 {
- self = .List(.Empty, val)
- } else {
- // this should raise an error
- }
- }
- }
- /** Delete the index-th node in the linked list, if the index is valid. */
- mutating func deleteAtIndex(_ index: Int) {
- if case var .List(next, value) = self {
- if index == 0 {
- self = next
- } else {
- next.deleteAtIndex(index - 1)
- self = .List(next, value)
- }
- } else {
- if index == 0 {
- self = .Empty
- } else {
- // this should raise an error, as the index is too big for this list
- }
- }
- }
- }
- class MyLinkedList {
- private var implList = LinkedList<Int>()
- /** Get the value of the index-th node in the linked list. If the index is invalid, return -1. */
- func get(_ index: Int) -> Int {
- do {
- return try implList.get(index)
- } catch {
- return -1
- }
- }
- /** 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. */
- func addAtHead(_ val: Int) {
- implList.addAtHead(val)
- }
- /** Append a node of value val to the last element of the linked list. */
- func addAtTail(_ val: Int) {
- implList.addAtTail(val)
- }
- /** 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. */
- func addAtIndex(_ index: Int, _ val: Int) {
- implList.addAtIndex(index, val)
- }
- /** Delete the index-th node in the linked list, if the index is valid. */
- func deleteAtIndex(_ index: Int) {
- implList.deleteAtIndex(index)
- }
- }
- func test_linkedlist() {
- var list = LinkedList<Int>()
- let ret_1: Int
- do {
- ret_1 = try list.get(0)
- } catch {
- ret_1 = -1
- }
- print(ret_1 == -1)
- print(list.length == 0)
- list.addAtHead(7)
- do {
- print(try list.get(0) == 7)
- } catch {
- print("false")
- }
- print(list.length == 1)
- list.addAtTail(5)
- print(list.length == 2)
- list.addAtIndex(1, 3)
- print(list.length == 3)
- list.deleteAtIndex(1)
- print(list.length == 2)
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement