[Day 15] 手牽手心連心！

11th鐵人賽 python scala golang rust

ryanyang1221

2019-10-02 22:50:24

2017 瀏覽

分享至

今天要來談的是，如何在這四個語言去實作出 Linked list。而 Linked list 是怎樣的資料結構呢？我們可以看到下面每個 Node 都有綠色和黃色的部分，綠色的是 Data，而黃色是指向下一個 Node 的 Pointer，因此可以看到 Node 間就會連成一個 list，所以就是所謂的 Linked list 啦！Linked list 還有一些變形像是 Doubly linked list，意思是一個 Node 不只指向下一個 Node 還會指向上一個 Node，這裡我們只會探討最一般的 Linked list。以下圖為例子，可以看到每次新增的 Node 都會在尾巴上接起來。 Linked list 比起一般的 Array，長度可以不用固定，也不需要事先 allocate 一塊 Memory。但如果要查找的話會比 Array 來得慢 (O(n) v.s. O(1))，插入跟刪除則是可以比 Array 來得快。詳細的比較可以參考這裡。那就讓我們來看看實作吧！

From Hackerrank

Python 3

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None 

def display(head):
  current = head
  while current:
    print(current.data, end=' ')
    current = current.next

def insert(head, data): 
  node = Node(data)
  if head is None:
    head = node
  else:
    current = head
    while(current.next is not None):
      current = current.next
    current.next = node
  return head

time = int(input())
head = None
for i in range(time):
    data = int(input())
    head = insert(head, data)  
display(head)

首先我們先定義出 class Node ，如同前面解釋， Node 有兩個 attribute， data 指的是資料， next 是指向下一個 Node。
insert 這個 Function 就是加入一個新的 Node ，基本思路就是找到最尾端的 Node ，把它的 next 設成新的 Node 。所以首先先建立新的 Node (node = Node(data))，假使一開始 List 剛建立，則 head 就是這個新創立的 Node 。但假如這個 List 已經存在，我們利用一個 while Loop，來找到最後一個 Node ，並且把它的 next 設成新創立的 Node 囉！
至於 display 則也是差不多的概念，用一個 while loop 一路把所有的 Node 的值給印出來。
其他 Linked List 常見的操作還有例如查找、刪除，可以自己試試看囉！

Golang

package main

import "fmt"

type Node struct {
  data int
  next *Node
}

func display(list *Node) {
  for p := list; p != nil; p = p.next {
   fmt.Println(p.data)
  }
}

func insert(newNode, list *Node) *Node {
  if list == nil {
    return list
  }
  for p := list; p != nil; p = p.next {
    if p.next == nil {
      p.next = newNode
      return list
    }
  }
  return list
}

func main() {
  node1 := &Node{1, nil}
  node2 := &Node{2, nil}

  list := node1
  list = insert(node2, list)

  display(list)
}

首先我們先定義一個 struct Node ，裡頭有一欄位是 data ，而另一個欄位 next 是指到下一個 Node 的 pointer。
而一開始我們先宣告一個 Node (&Node{1, nil}) 並取其 Pointer。接著我們來看 insert 這個 Function。第一個參數 newNode是要拿來加入的新 Node，第二個則是目前的 list (也就是指向 Head 的 Pointer)。其中正常情況會進到裡頭的 for loop，每次都找看看當前 Node 的 next 是不是 nil ，如果是的話就把 next 指向新的 Node，也就是參數 newNode 。
display 的概念就是從 list 的 Head 出發，一路把每個 Node 的 data 印出來。

Rust

struct Node {
    data: i32,
    next: Option<Box<Node>>
}

impl Node {
    fn from(d: i32) -> Node {
        Node {data: d, next: None}
    }

    fn add_to_tail(&mut self, data: i32) {
        let mut curr = self;
        loop {
            match &curr.next {
                None => break,
                Some(node) => curr = curr.next.as_mut().unwrap()
            }
        }
        curr.next = Some(Box::from(Node::from(data)));
    }
}

fn insert(mut head: Option<Box<Node>>, data: i32) -> Option<Box<Node>> {
    if head.is_none() {
        Some(Box::new(Node{data, next: None}))
    } else {
        head.as_mut().unwrap().add_to_tail(data);
        head
    }
}

fn display(head: &Option<Box<Node>>) -> String {
    let mut res = "".to_string();

    let mut curr: &Option<Box<Node>> = head;
    while curr.is_some() {
        let node = curr.as_ref().unwrap();
        print!("{} ", node.data);
        curr = &node.next;
    }
    
}


pub fn main() {
    let mut head: Option<Box<Node>> = None;
    head = insert(head, 1);
    head = insert(head, 2);
    display(&head);
}

這裡看到跟其他語言有點不一樣的是，在 Struct Node 的 next 不是直接寫上 Node 而是 Box<Node>，這是因為 Rust 在 Compile 的時候，必須去決定每個型別應該要配置多少的記憶體空間，然而目前這種遞迴結構會讓 Compiler 不知道要怎麼決定配置大小 (因為會無限循環)，而 Box<型別> 是一個智慧指標，會把 Node "裝箱" 配置在 Heap 上，並且此指標指向該值分配的位置，這樣子 Compiler 就知道 next 只要配置一個指標的大小。然而又因為 Rust 並沒有所謂的 Null pointer，所以這邊必須再將 Box<Node> 包在 Option 裡面，所以就變成 next: Option<Box<Node>>
接下來 impl Node 我們為 Node 建立一些方法(method)和關聯函數(associated function)。fn from(d: i32) -> Node 是一個關聯函數，做的事情就是為我們建立一個新的 Node (根據 Input data)。fn add_to_tail(&mut self, data: i32) 則是當有新的資料進來的時候，建立一個新 Node，並把原先最尾端的 Node 的 next 指向他。跟其他語言概念一樣，也是先去找到最尾端的 Node。Input 的 &mut self指的是呼叫這個方法的 Node 本身，除了把他借來並且也希望能夠修改。loop 做的事情就是試著找到最後一個 Node 且 next 是 None 的，為了找出來也搭配了 match。這裡 match 了 &curr.next，如果直接寫 curr.next 會有 Error cannot move out of borrowed content，因為你不能把借來的東西再做轉移，所以必須要再借 curr.next。而當 curr.next 是 Some(node) 時，就把目前的 curr 改成是 curr.next.as_mut().unwrap()，這裡一大串概念上是 curr.next 是個 Option，配合as_mut().unwrap() 可以得到一個可變的 Reference，也就是下一個 Node (這裡比較複雜，可以看看 Rust 闡述所有權的概念)，直到 curr.next 是 None 就跳出 loop。接著 curr.next = Some(Box::from(Node::from(data))); 來指到一個新的 Node。
再來看另外兩個函式。第一個是 insert，這是最外層用來把資料塞進 List 用的，所以第一個參數我們會放入 List 的 Head，假使 Head 一開始是 None 那麼當然就是為他創一個新的 Node，但如果不是，我們就會 head.as_mut().unwrap().add_to_tail(data)，做的事情其實就是將 Option 透過 as_mut() 轉換後得到的可變 Reference 取出，並且呼叫我們剛才解釋的 add_to_tail(data) 來把新的資料加到最尾端，就得到新的 List。最後是 display，就是去 Iterate 這個 List，並把 data 持續印出。curr.as_ref().unwrap() 跟概念跟剛才談到的類似，只是這裡拿到的是不可變的 Reference，因為我們並沒有要進行改動囉！