如何用数组实现链表

不知道和leetcode 707是不是同一个意思，我这实现了707的，等会再看看大佬们的答案。 Python版：

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

class MyLinkedList:
    def __init__(self):
        self.head = Node(0) # 哨兵节点，伪头节点，不存储数据
        self.size = 0

    def get(self, index: int) -> int:
        if index < 0 or index >= self.size:
            return -1
        prev = self.head
        for _ in range(index + 1):
            prev = prev.next
        return prev.val

    def addAtHead(self, val: int) -> None:
        self.addAtIndex(0, val)

    def addAtTail(self, val: int) -> None:
        self.addAtIndex(self.size, val)

    def addAtIndex(self, index: int, val: int) -> None:
        if index > self.size or index < 0:
            return
        self.size += 1
        prev = self.head
        for _ in range(index): ## 找到index下标对应的前置节点。如果index=0,这段for循环不执行
            prev = prev.next
        node = Node(val)
        node.next = prev.next
        prev.next = node

    def deleteAtIndex(self, index: int) -> None:
        if index >= self.size or index < 0:
            return
        self.size -= 1
        ## 先找到前置节点
        prev = self.head
        for _ in range(index):
            prev = prev.next ## 前置节点为prev
        node = prev.next  ## node为待删除节点
        prev.next = node.next
        del node 

我们可以用数组的值来表示传统链表的next指针，数组的值指向的是链表下一项的索引。

为了简单起见，我们约定头指针初始化指向数组第一项。 我们拿arr = [1,3,5,2, -1, 4] 来说。

初始化头指针指向索引0，索引为0的值为1，也就是说其下一项为arr[1]，我们继续看arr[1] 值为3，也就是说next应该是arr[3] 。。。

PS：

实际上我只实现了一半，还有一些问题需要解决，但是思路都差不多。 这些留给读者自己实现（包括代码以及扩展）。

我弃坑了。。。

使用静态链表的场景应该是：所需的存储空间是固定的，那我们用数组来模拟链表就可以省去了诸如往数组里插入元素时其后的元素都需要后移一个位置这种消耗。

下面的实现中，每个数组元素都是一个对象，value 是节点的值，next 是下一个节点的坐标，head 保存链表中第一个元素在数组中的下标。

新增链表节点时，先在数组中找到一个空位存放这个节点，然后按照链表的常规操作，找到链表的尾端，把那个节点的 next 改为新节点的下标。

class StaticList {
  constructor(size) {
    this.list = Array(size)
    this.head = null
  }

  // Append a new item to the end of the linked list.
  append(value) {
    // Store the new item and get the index of the stored place.
    const pos = this._put(value)

    // Find the last item of the linked list.
    // Set its next to the index of the new item.
    const tail = this.get(this.len() - 1)
    if (!this.head) {
      this.head = this.list[pos]
    } else {
      tail.next = pos
    }

  }

  // Get the nth item of the linked list.
  get(n) {
    if (n >= 0) {
      let cur = this.head
      while (n > 0) {
        cur = this.list[cur.next]
        n--
      }
      return cur
    }
  }

  // Find an empty space in the array, put the new item in.
  // And return the corresponding index.
  _put(value) {
    const available = this.list.findIndex(item => !item)
    const node = new Node(value)
    this.list[available] = node
    return available
  }

  // Get the length of the linked list.
  len() {
    let cur = this.head
    let count = 0
    while (cur) {
      count++
      cur = this.list[cur.next]
    }
    return count
  }

  // Insert an item in the given position.
  insert(index, value) {
    const pos = this._put(value)

    // Find the item previous to the intended index.
    const previous = this.get(index - 1)
    this.list[pos].next = previous.next
    previous.next = pos

  }
}

class Node {
  constructor(value) {
    this.value = value
    this.next = -1
  }
}

const list = new StaticList(6)
list.append(0)
list.append(3)
list.insert(1, 1)
list.append(4)
list.append(5)
list.insert(2, 2)