## 线性表

### 线性结构特点:

<ul>
  <li>存在唯一的一个被称做“第一个”的数据元素</li>
  <li>存在唯一的一个被称做“最后一个”的数据元素</li>
  <li>除第一个外，集合中的每个数据元素均有一个前驱</li>
  <li>除最后一个外，集合中的每个数据元素均有一个后继</li>
</ul>

### 线性表的顺序存储结构 - 顺序表

#### 基本形态

```javascript
    1 . 顺序表空
        - 条件: L.length == 0
        - 操作: 不允许删除操作

    2 . 顺序表满
        - 条件: L.length == MaxLength
        - 操作: 不允许插入操作

    3 . 不空也不满
        - 条件: 0 < L.length < MaxLength
        - 操作: 可以插入，可以删除
```

#### 基本算法

```javascript
    // 遍历
    // 顺序访问所有元素
    for (let i = 0; i < L.length; i++) {
      Visit(L.elem[i])
    }

    // 查找元素 x
    for (let i = 0; i < L.length; i++) {
      if (L.elem[i] == x) {
        ...
      }
    }
```

```javascript
    插入
     - 条件: 表不满，插入的范围合理
     - 步骤: 第 i 至最后元素后移一个元素，第 i 个位置插入元素 x， 表长增加1

    function listInsert(L, i, x) {
      if (L.length === MaxLength || i < 1 || i > L.length + 1) {
        return false
      }

      // 长度为4，往第二个位置插入，j = 4-1; j > 2-1; j--
      // L.elem[4] = L.elem[3]
      // L.elem[3] = L.elem[2]

      // 第 i 至最后元素后移一个元素
      for (let j = L.length - 1; j >= i-1; j--) {
        L.elem[j+1] = L.elem[j]
      }

      // 第 i 个位置插入元素 x
      L.elem[i-1] = x // L.elem[2-1] = x

      // 表长增加1
      L.length++
      return true
    }
```

```javascript
  删除
   - 条件: 表不为空, 范围合理
   - 步骤: 取出第 i 个元素，将第 i 个元素之后的元素向前移一个位置，表长减1

  function listDelete (L, i) {
    if (L.length === 0 || i < 1 || i > L.length) {
      return false
    }
    // 删除第二个位置元素，先取出， x = L.elem[2-1] ，也就是 第二个元素的值
    var  x = L.elem[i-1]

    // 第 i 个元素之后的元素向前移一个位置
    for (let j = i; j < L.length; j++) {
      L.elem[j-1] = L.elem[j]
    }

    // 表长减1
    L.length--

    return true
  }

```

#### 算法分析

<img src='./image/biao-1.png' width=600 />

---

### 线性表的链式存储结构 - 单链表

顺序存储结构特点是逻辑关系上相邻的两个元素在物理位置上也相邻，因此可以随机存取表中的任一元素，它的存储位置可用一个简单直观的公式来表示。然而，在做插入和删除的时候，需要大量移动元素。

而链式存储结构特点是用一组任意的存储单元存储线性表的数据元素(这组存储单元可以是连续的，也可以是不连续的)

数据元素 a(i) 除了本身信息外，还需要一个指示其直接后继的信息，这两部分信息组成数据元素 a(i) 的存储映像，称为<em>结点</em>。它包含两个域: <em>数据域</em> (存储数据元素信息) 和 <em>指针域</em> (存储直接后继位置)

<!--more-->

> 整个链表的存储必须从头指针开始进行，头指针指示链表中的第一个结点的存储位置。同时，由于最后一个数据元素没有直接后继，则线性链表中最后一个结点的指针为 "空"(NULL)

<img src='./image/biao-2.png' width=400 />

```javascript
  从上图我们可以得出
   - 头指针H， 指向31的存储位置，31存储的数据域为 ZHAO, 指针域指向 7的存储位置
   - 7存储的数据域为 QIAN, 指针域指向 13 的存储位置
   - ...

   (所以链表中的顺序为: 看下图)
```

<img src='./image/biao-3.png' width=500 />

有时在单链表的第一个结点之前附设一个结点，称之为 <em>头结点</em>，头结点的数据域可以不存储任何信息(当然也可以存储比如表长度等附加信息)，头结点的指针域存储指向第一个结点的指针(即第一个元素结点的存储位置)，如果表为空表，则头结点的指针域为"空"

<img src='./image/biao-4.png' width=520 />

```javascript
  // 单链表中，任何两个元素的存储位置之间没有固定的联系

  // 每个元素的储存位置都包含在其直接前驱结点的信息之中

  // p 结点 则指指针p 所指向的结点(即其存储位置存放在p中的结点)， 如果实在没搞懂，可以理解成 p 就是a(i)

  假设 p 是指向单链表中的第 i 个数据元素( 结点a(i) ) 的指针， 则
   p -> next 是指向 第 i+1 个数据元素( 结点a(i+1) ) 的指针

  // 换句话说
  p -> data = a(i) // p -> data 是指 a(i) 结点中的数据域
  p -> next -> data = a(i+1) // p -> next 是指 下一个结点的存储位置

```

这里封装了常见的方法

|           方法            |                描述                 |
| :-----------------------: | :---------------------------------: |
|      append(element)      |     向链表尾部添加结点 element      |
| insert(position, element) | 向位置 position 处插入结点 element  |
|    removeAt(position)     |    按照索引值 position 删除结点     |
|      remove(element)      |     搜索并删除给定结点 element      |
|       removeTail()        |       删除链表中最后一个结点        |
|     indexOf(element)      | 查找并返回给定结点 element 的索引值 |
|         isEmpty()         |          判断链表是否为空           |
|           size            |            获取链表长度             |
|        toString()         |          转换为字符串输出           |
|         getHead()         |             获取头结点              |
|         getTail()         |             获取尾结点              |
|          show()           |       打印当前链表的所有结点        |

#### 实现一个单链表

```javascript
// 核心要点就是，两个指针，一个 previous ，一个current

// previous = current， 保存前一个指针指向的结点，然后 current 指针移动

// 当current指针到了我们要操作的结点，比如要删除一个结点c， 那么 previous.next(b结点) = current.next (d结点)，因为previous指向b结点，current指向的是c结点，所以previous(b结点)的后继指向current(c结点)的后继，也就是结点d的前置

function linkList() {
  // 定义结点的函数
  var Node = function(element) {
    this.element = element; // 存放结点内容，也就是数据域
    this.next = null; // 指针域
  };

  var length = 0; // 链表长度
  var head = new Node('head'); // 定义头指针，头指针的数据域存储信息 head ，头指针的 next = null
  length++;
  // 向链表尾部添加结点element
  this.append = function(element) {
    var node = new Node(element);
    var current; // 操作所用到的指针

    if (!head) {
      head = node;
    } else {
      current = head;
      while (current.next) {
        current = current.next;
      }
      current.next = node;
    }
    length++;
    return true;
  };

  // 向位置position处插入结点element
  this.insert = function(position, element) {
    // 排除表满 | 插入位置不正确 的情况
    console.log(length);
    if (position < 0 || position > length) {
      return false;
    } else {
      var insertNode = new Node(element);
      var ins_current = head; // 当前插入指针指向头指针
      var _previous = '';
      var index = 0;

      if (position === 0) {
        insertNode.next = ins_current; // 插入位置为第一个，则在头指针前
        head = insertNode;
      } else {
        while (index++ < position) {
          _previous = ins_current; // 当前的_previous指向头指针
          ins_current = ins_current.next; // 当前的指针指向 头指针的下一个结点
        }
        _previous.next = insertNode;
        insertNode.next = ins_current;
      }
    }

    length++;
    return true;
  };

  // 按照索引值position删除结点
  this.removeAt = function(position) {
    // 排除表空 | 位置不合理 的情况
    if (position < 0 || position > length) {
      return false;
    } else {
      var reAtCurrent = head;
      var reAtPrevious = '';
      var index = 0;

      if (position === 0) {
        // 删除头指针指向的结点
        head = reAtCurrent.next; // 当前的头指针指向下一结点
      } else {
        while (index++ < position) {
          reAtPrevious = reAtCurrent; // reAtPrevious指针指向头指针head
          reAtCurrent = reAtCurrent.next; // reAtCurrent指针指向下一个结点 a (这里假设position = 1，也就是删除结点a)
        }
        reAtPrevious.next = reAtCurrent.next; // head的下一个结点 = a的下一个结点b。 也就是 head.next = b
      }

      length--;
      return reAtCurrent.element; // 这就是要删除的结点的数据域
    }
  };

  // 搜索并删除给定结点element
  this.remove = function(element) {
    var reCurrent = head;
    var rePrevious = '';

    if (element === reCurrent.element) {
      // 当前删除的是头结点
      head = reCurrent.next; // 头指针指向下一个结点
      length--;
      return true;
    }

    rePrevious = reCurrent;
    reCurrent = reCurrent.next; // 当前的指针指向头结点的下一个结点，从下一个结点开始查找

    while (reCurrent) {
      // 不能写成 reCurrent.next != null ，假设删的是最后一个结点，而最后一个结点的next = null
      if (element === reCurrent.element) {
        rePrevious.next = reCurrent.next;
        length--;
        return true;
      } else {
        rePrevious = reCurrent;
        reCurrent = reCurrent.next;
      }
    }
    return false;
  };

  // 删除链表的最后一个结点
  this.removeTail = function() {
    if (length < 1) {
      return false;
    }

    var reTailCurrent = head;
    var reTailPrevious = '';

    if (length === 1) {
      // 整个链表只有一个头结点，删除头结点，头指针指向null，表示表空
      head = null;
      length--;
      return reTailCurrent.element; // 返回删除的结点的数据域
    }

    while (reTailCurrent.next !== null) {
      reTailPrevious = reTailCurrent;
      reTailCurrent = reTailCurrent.next;
    }

    reTailPrevious.next = null;
    length--;
    return reTailCurrent.element; // 返回被删除的结点的数据域
  };

  // 判断链表是否为空
  this.isEmpty = function() {
    if (length === 0) {
      return true;
    } else {
      return false;
    }
  };

  // 获取链表的长度
  this.size = function() {
    return length;
  };

  // 转化为字符串输出
  this.toString = function() {
    var strCurrent = head;
    var string = '';
    while (strCurrent) {
      // 不能写成 strCurrent.next != null ，因为还要把最后一个结点的element打印出，而最后一个结点的next = null
      string += strCurrent.element;
      strCurrent = strCurrent.next;
    }
    // console.log(string)
    return string;
  };

  // 获取头结点
  this.getHead = function() {
    return head;
  };

  // 获取尾结点
  this.getTail = function() {
    if (length === 0) {
      return false;
    }
    var tailNode = '';
    var tailCurrent = head;
    while (tailCurrent) {
      if (tailCurrent.next === null) {
        tailNode = tailCurrent;
        break;
      } else {
        tailCurrent = tailCurrent.next;
      }
    }
    return tailNode;
  };

  // 打印当前链表的所有结点
  this.show = function() {
    var currentNode = head;
    var result = '';
    while (currentNode.next != null) {
      result = result + currentNode.next.element + ' . '; // 不显示头结点, 然后从头结点的下一个结点开始输出数据域的内容
      currentNode = currentNode.next;
    }
    return result;
  };
}

var list = new linkList();
list.append('a');
list.append('b');
list.append('c');
list.append('d');
// list.insert(5, 'e')
// list.removeAt(1)
// list.remove('e')
// list.isEmpty()
list.getTail();
// console.log(list.show())
```

#### 实现一个双向链表

```javascript
function linkList() {
  // 定义一个结点
  var Node = function(element) {
    this.element = element; // 存放结点内容，也就是数据域
    this.next = null; // 后继
    this.front = null; // 前驱
  };
  var length = 0;
  var head = new Node('head');
  length++;

  // 查找，找到于item内容相同的element，则返回该结点，找不到返回空
  this.find = function(item) {
    var resNode = null;
    var currentNode = head;
    while (currentNode) {
      if (currentNode.element === item) {
        resNode = currentNode;
        break;
      } else {
        currentNode = currentNode.next;
      }
    }
    return resNode;
  };

  // 插入, element 为新插入的结点，item为要插入的前一个结点
  this.insert = function(element, item) {
    var newNode = new Node(element);
    var currentNode = this.find(item); // 找到这个结点，以这个结点为当前结点
    newNode.next = currentNode.next;
    newNode.front = currentNode;
    currentNode.next = newNode;
  };

  // 删除, item 为需要删除的结点
  this.remove = function(item) {
    var currentNode = this.find(item);
    if (currentNode.next != null) {
      // 不是最后一个结点
      currentNode.front.next = currentNode.next; //让前驱节点指向需要删除的节点的下一个节点
      currentNode.next.front = currentNode.front; // //让后继节点指向需要删除的节点的上一个节点
      currentNode.next = null;
      currentNode.front = null;
    }
  };

  // 打印当前链表的所有结点
  this.show = function() {
    var currentNode = head;
    var result = '';
    while (currentNode.next != null) {
      result = result + currentNode.next.element + ' . '; // 不显示头结点, 然后从头结点的下一个结点开始输出数据域的内容
      currentNode = currentNode.next;
    }
    return result;
  };
}

var list = new linkList();
list.insert('a', 'head');
list.insert('b', 'a');
list.insert('c', 'b');
list.remove('b');
console.log(list.show());
```

### 应用场景 合并有序链表

```javascript
将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例：

输入：[1, 2, 3], [1, 3, 4] // 1->2->3  1->3->4
输出：[1, 1, 2, 3, 3, 4] // 1->1->2->3->4->4


var linkList = function () {
  var ListNode = function (val) {
    this.val = val
    this.next = null
  }
  this.length = 0
  var head = new ListNode('head')
  var current = ''
  this.length++

  this.append = function (val) {
    let node = new ListNode(val)
    if (!this.head) {
      this.head = node
    } else {
      current = head
      while (current.next) {
        current = current.next
      }
      current.next = node
    }
    this.length++
  }
}

var mergeTwoList = function (list1, list2) {
  var arr = []
  var list = new linkList()

  // 第一个链表的头结点
  var head1 = list1.head
  // 第二个链表的头结点
  var head2 = list2.head

  // 把第一个链表的所有key存进数组
  while (head1) {
    array.push(head1.key);
    head1 = head1.next;
  }

  // 把第二个链表的所有key存进数组
  while (head2) {
      array.push(head2.key);
      head2 = head2.next;
  }

  // 将两个链表的key插入到新链表中
  while (list1 && list2) {
    if (current1.key) {}
  }
}

var l1 = [1,2,3]
var l2 = [1,3,4]
var list1 = new linkList()
var list2 = new linkList()

l1.forEach((key) => {
  list1.append(key)
})

l2.forEach((key) => {
  list1.append(key)
})

var list = mergeTwoList()

```

### 应用场景 翻转链表

```javascript

反转一个单链表。

示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

```

```javascript

// 来自 leetcode.com 的第206题

var reverseList = function(head) {
  if (!head || !head.next) {
    return head
  }

  var current = head
  var n = null
  var next

  while (current !== null) {
    next = current.next
    current.next = n
    n = current
    current = next
  }

  return n
}

// 解读

输入 1 -> 2 -> 3 -> 4 -> 5 -> NULL
输出 5 -> 4 -> 3 -> 2 -> 1 -> NULL

head = 结点1
current = head = 结点1
n = null
next = undefined

while (current !== null) { // 也就是current = head = 结点一 不是 空结点
  // 第一轮
  next = current.next // 结点2
  current.next = n    // null   也就是结点1的next为null  1 -> NULL
  n = current         // 结点1
  current = next      // 结点2

  // 第二轮
  next = current.next // 结点3
  current.next = n    // 结点1 ， 也就是结点2的next为结点1  2 -> 1
  n = current         // 结点2
  current = next      // 结点3

  // 第三轮
  next = current.next // 结点4
  current.next = n    // 结点2    也就是结点3的next为结点2  3 -> 2 -> 1
  n = current         // 结点3
  current = next      // 结点4

  // 以此类推
  ...
  ...

  // 思路就是用两个指针，一个(next)存储当前结点(current)的下一结点，一个指针(n)存储当前结点，将下一结点的next指向n
}
```