5-单向链表

关于链表：
链表是非常常见用于存储数据的线性结构。
链表和数组一样，可以用于存储一系列的元素，但是链表和数组的实现机制完全不同。

数组：

• 在储存多个元素，数组（或称之为列表）可能事最常用的数据结构。
  
• 我们之前说过，几乎每一种编程语言都有默认实现数组结构。
  
• 但是数组也有很多缺点：
  
  • 数组的创建通常需要申请一段连续的内存空间（一整块的内存），并且大小事固定的(大多数编程语言都是固定的，) 所以当当前数组不能满足容量需求时，需要扩容。（一般情况下是申请一个更大的数组，比如2倍，然后将原数组中的元素复制过去）
    
  • 而且在数组开头或中间位置插入数据的成本很高，需要进行大量的位移。
    
  • 尽管我们已经学过的JavaScript的Array类方法可以帮我们做这些事，但是背后的原理依然是这样。
    

链表的优势

• 要存储多个元素，另外一个选择就是链表。
  
• 但不同于数组，链表中的元素在内存中不必是连续的空间。
  
• 链表的每个元素由一个存储元素本身的节点和一个指向下一个元素的引用（有些语言成为指针或者连接）组成。
  
• 相对于数组，链表的优点：
  
  • 内存空间不是必须连续的，可以充分利用计算机的内存，实现灵活的内存动态管理。
    
  • 链表不必在创建时就确定大小，并且大小可以无限的延申下去。
    
  • 链表在插入和删除数据时，时间复杂度可以达到O(1)，相对数组效率高很多。（大O表示法）
    
• 相对数组，链表有一些缺点：
  
  • 链表访问任何一个位置的元素时，都需要从头开始访问。（无法跳过第一个元素访问任何一个元素）
    
  • 无法通过下标直接访问元素，需要从头一个个访问，知道找到对应的元素。
    

链表的结构：
什么是链表：
链表类似于火车：有一个火车头，火车会连接一个节点，节点上有乘客（类似于数据），并且这个节点会连续下一个节点，以此类推。
链表的火车结构：

封装一个链表类

1. 封装LinkedList的类，用于表示我们的链表结构。
   
2. 在LinkedList类中有一个Node类，用于封装每一个节点上的信息。（和优先级队列的封装一样）
   
3. 链表中我们保存两个属性，一个是链表的长度，一个是链表中第一个节点。
   

01-单向链表结构：
function LinkedList() {
// 内部的类：节点类
function Node(data) {
this.data = data;
this.next = null;

// 属性，那个头部。
this.head = null;
this.length = 0;
}
}**

链表常见操作：

• 我们先来认识一下，链表中应该有哪些常见的操作。
  
  • append（element）：向列表尾部添加一个新的项。
    
  • insert（position,element）：向列表的特定位置插入一个新的项。
    
  • get（position）：获取对应位置元素。
    
  • indexOf（element）：返回元素在列表中的索引，如果列表中没有该元素则返回-1。
    
  • update（position）：修改某个位置的元素。
    
  • removeAt（position）：从列表的特定位置移除某一项。
    
  • remove（element）：从列表中移除一项。
    
  • isEmpty（）：如果链表中不包含任何元素，返回true，如果链表长度大于0则返回false。
    
  • size（）：返回链表包含的元素个数。于数组的length属性类似。
    
  • toString（）：由于列表使用了Node类，就需要重写继承自JavaScript对象默认的tiString方法，让其只输出元素的值。
    
• 链表的操作方法和数组非常类似，因为链表本身就是一一种可以代替数组的结构。
  

链表方法

append方法**
向链表尾部加数据可能有两种情况：

1. 链表本身为空，新添加的数据时唯一的节点。
   
2. 链表不为空，需要向其它节点后面追加节点。
   

append 代码：
// 1.追加方法。
LinkedList.prototype.append = function (data) {
// 1.1 创建新的节点。
var newNode = new Node(data);


// 1.2 判断是否添加第一个节点(前面是否有节点)
if (this.length == 0) { // 1.2.1 第一个节点。
this.head = newNode;
} else { // 2.1.2 不是第一个节点
let current = this.head;
while (current.next) { // 1.2.2 判断是否是空不是空则，去拿下一个对象。
current = current.next;
}
current.next = newNode;
}
// 1.2.3 自增 length。
this.length += 1;
}


toString方法

• 该方法比较简单，主要是获取每一个元素。
  
• 还是从head开头，因为获取链表的任何元素都必须从第一个节点开头。
  
• 循环遍历每一个节点，并且取出其中的element，拼接成字符串。
  
• 将最终字符返回
  

toString 代码：
// 2. toString 方法
LinkedList.prototype.toString = function () {
let current = this.head;
let linkString = “”;
if (current) {
while (current) {
linkString += current.data;
current = current.next;
}
} else {
console.log(“空的不行”)
}
return linkString;
}

inert方法

• 添加到第一个位置：
  
  • 添加到第一个位置，表示新添加的节点是头，就需要将原来的头结点，作为新节点的next。
    
  • 另外这个时候的head应该指向新节点。
    

• 添加到其它位置：
  
  • 如果是添加到其它位置，就需要先找到这个节点位置了。
    
  • 可以通过whlie循环，一点点向下找，并且在这个过程中保存上一个节点和下一个节点。
    
  • 找到正确的位置后，将新节点的next指向下一个节点，将上一个节点的next指向新的节点。
    

insert 代码：
// 3.insert 方法
LinkedList.prototype.insert = function (position, data) {
//3.1 对position进行越界判断
if (position < 0 || position > this.length) {
return false;
}
// 3.2 根据data创建节点
let newNode = new Node(data);


// 3.3 判断position是不是 0
if (position == 0) {
newNode.next = this.head;
this.head = newNode;
} else {
let index = 0;
let current = this.head;
let previous = null;
while (index++ < position) {
previous = current;
current = current.next;
}
newNode.next = current;
previous.next = newNode;
}
this.length += 1;
return true;
}

get 方法
通过提供一个整型的参数来做位置，获取链表结构对应的数据。
再只需要去链表结构里一层一层的拿就可以了。
get 代码：
// 4.get 方法
LinkedList.prototype.get = function (position) {
if (position < 0 || position >= this.length) {
return null;
} else {
current = this.head;
for (let i = 0; i < position; i++) {
current = current.next;
}
return current.data;
}
}

indexOf 方法
返回元素在列表中的索引，如果列表中没有该元素则返回-1。
indexOf 代码：
// 5.indexOf 方法
LinkedList.prototype.indexOf = function (element) {
let index = 0;
let current = this.head;


while (current) {
if (current.data == element) {
return index
}
current = current.next;
index += 1;
}
return -1;
}

upDate 方法
修改某个位置的元素。
upDate 代码
// 6.upDate 方法
LinkedList.prototype.upDate = function (position, element) {
if (position < 0 || position >= this.length) {
return null;
} else {
let current = this.head;
for (let i = 0; i < position; i++) {
current = current.next;
}
current.data = element;
}
}

removeAt 方法
从列表的某个位置移除一项。
removeAt 代码
// 7.removeAt 方法
LinkedList.prototype.removeAt = function (position) {
if (position < 0 || position >= this.length) {
return null;
} else {
let current = this.head;
if (position == 0) {
this.head = this.head.next;
} else {
let index = 0;
let previous = null;
while (index++ < position) {
previous = current;
current = current.next;
}
previous.next = current.next;
}
this.length -= 1;
return current.data;
}
}

remove 方法
从列表移除某个指定的元素。
remove 代码
// 8.remove 方法 采用已有方法调用即可。
LinkedList.prototype.remove = function (element) {
// 1. 获取date在列表中的位置。
let position = this.indexOf(element);
// 2.根据位置信息，删除节点。
return this.removeAt(position);
}

isEmpty 方法
如果链表中不包含任何元素，返回true，如果链表长度大于0则返回false。
isEmpty 代码：
// 9.isEmpty
LinkedList.prototype.isEmpty = function (){
return this.length == 0;
}

size 方法
返回链表包含的元素个数。于数组的length属性类似。
代码：
LinkedList.prototype.size = function () {
return this.length
}