資料結構

1// Array: element i lives at base + 8 * i, so reaching it is one step.
2function arrayGet(a: number[], i: number): number {
3  return a[i];
4}
5 
6function arraySum(a: number[]): number {
7  let total = 0;
8  for (let i = 0; i < a.length; i++) total += a[i];
9  return total;
10}
11 
12function arrayInsert(a: number[], at: number, value: number): void {
13  a.push(0);
14  for (let i = a.length - 1; i > at; i--) a[i] = a[i - 1];
15  a[at] = value;
16}
17 
18// Linked list: each node knows only where the next one is.
19class ListNode {
20  next: ListNode | null = null;
21  constructor(public value: number) {}
22}
23 
24function listGet(head: ListNode, i: number): number {
25  let node = head;
26  for (let k = 0; k < i; k++) node = node.next!;
27  return node.value;
28}
29 
30function listSum(head: ListNode | null): number {
31  let total = 0;
32  for (let node = head; node; node = node.next) total += node.value;
33  return total;
34}
35 
36function listInsert(head: ListNode | null, at: number, value: number): ListNode {
37  const fresh = new ListNode(value);
38  if (at === 0) {
39    fresh.next = head;
40    return fresh;
41  }
42  let prev = head!;
43  for (let k = 1; k < at; k++) prev = prev.next!;
44  fresh.next = prev.next;
45  prev.next = fresh;
46  return head!;
47}