js数据结构[单项链表]；

链表数据结构

什么是链表：
链表存储有序的元素集合，组，链表中的元素在内存中并不是连续放置的。每个元素由一个存储元素本身的节点和一个指向下一个元素的引用（也称指针或链接）组成。
链表跟数组的区别 （只是简单叙述。）

1. 数组对比链表的优点：数组比较 方便 提供 arr[ i ] 就能够访问到元素。
2. 数组的缺点：每次从数组的起点或者从中间插入或者移除的成本很高 。
3. 数组的另一个细节是可以直接访问任何位置的任何元素，而要想访问链表中间的一个元素，需要从起点（表头）开始迭代列表直到找到所需的元素。

链表的优点：

1. 添加或移除元素的时候不需要移动其他元素。**
2. 内存空间不是连续的，可以充分利用计算机的内存实现灵活动态管理。
3. 链表不必在创建时确定大小，并且大小可以无限延伸下去。
4. 链表在插入数据时候 时间复杂度可以做到O(1)相对数组效率较高。

封装一个单向链表。

1. 只能从头遍历到尾或者从尾部遍历到头部。
2. 整个链表想连的过程是单项的。
3. 实现原理是上一个链表中有一个指向下一个的引用。
4. 缺点： 可以轻松到达下一个节点，但是很难回到上一个节点。

封装链表

看图可以知道一个单向链表 是有一个 head属性 用来指向第一个节点 所以 this.head = newNode，然后 新节点 还有 两个属性分别是 itme 和next 所以实例化一个内部类(函数)。next用来指向下一个节点，此外还需要一个length 用来记录链表的长度。代码

//初始化一个 单项链表
function LinkedList(){
	function Node(data,next){
		this.data = data;
		this.next = next;
	}
	this.head = null  //默认为空
	this.length = 0;
}
1
2
3
4
5
6
7
8
9

单向链表的追加方法

单向链表如果要新增一个 元素那么该如何添加呢？ 有几种添加情况呢？

1. 链表内没有元素直接就可以 将传过来的数据 插入到 头顶 如何判断是不是第一个呢？this.length ==0， this. head = newNode;
2. 如果不是第一个元素那么就 直接从头开始遍历 到最后一个节点 用最后节点的 next 指向新元素

LinkedList.prototype.append = function(){
//链表内没有元素直接就可以 将传过来的数据 插入到 头顶  如何判断是不是第一个呢
	let newNode = new Node(data,next)
	if(this.length ==0){
		this.head = newNode
	}else {
	//如果不是第一个元素那么就 直接从头开始遍历 到最后一个节点 用最后节点的 next 指向新元素
		while(current.next){
			current = current.next;
		}
		current.next = newNode;
		this.length +1;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

insert 插入方法

单向链表插入的话如何实现？插入也是有两种情况

1. 首先给他添加一个要插入的位置参数和要插入的数据，然后对插入的位置进行越界判断，如果position < 0 或者 传入的位置大于等于length 直接return false。
2. 判断插入的位置是不是第一个位置 ，如果是第一个,this.head 指向的就是第一个就先把 newNode的next 指向更改为this.head.next ，newNode.next = this.head; 在将原来的元素 赋值为新的元素 this.head = newNode
3. 如果不是开始遍历 找到 传入的位置，然后 位置前的一个元素 指向新的 元素 新元素的 next 指向下一个元素， 需要多添加一个变量用来保存 传入位置的上一个元素。代码
   

LinkedList.prototype.append = function(position,data){
 if (position < 0 || position > this.length) return false;
	let newNode = new Node()
	//判断插入的位置是否是第一个位置。
	if(position==0){
		newNode.next = this.head.next;
		this.head = newNode;
	}else {
		let index = 0;
		let current = this.head;
		let prev = null;
		while(index++ < positon){
		prev = current
		//current 一直遍历到当前要插入的位置。
		current = current.next;
		}
		newNode.next = current
		prev.next = newNode;
	}
	this.length +=1;
	return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

removeAt方法

根据传入的位置移除位置的元素。

1. 越界判断
2. 判断是否删除的是第一个节点

  LinkedList.prototype.removeAt = function (position) {
	 //1.越界判断
	 if (position < 0 || position >= this.length) return null;
	//2.判断是否删除的是第一个节点
	let current = this.head;
	if(position == 0){
		this.head = this.head.next;
	}else {
		let index = 0;
		let prev = null;
		while(index++ < positon){
			prev = current;
			current = current.next;
		}
		prev.next = current.next;
	}
	this.length-=1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

update方法。

1. 越界判断
2. 找到正确节点
3. 修改节点的data

 LinkedList.prototype.update = function (position, newData) {
                // 1.越界判断
                if (position < 0 || position >= this.length) return false;

                // 2.查找正确的节点
                let current = this.head;
                let index = 0;
                while (index++ < position) {
                    current = current.next
                }
                // 3.将positon位置的node的data修改成新的newData;
                current.data = newData;
                return true;
            }
1
2
3
4
5
6
7
8
9
10
11
12
13
14

其他方法

LinkedList.prototype.toString = function () {
                // 定义变量 current
                let current = this.head;
                let listString = "";
                // 循环获取一个个的节点 
                while (current) {
                    listString += current.data + " "
                    current = current.next;
                }
                return listString
            }
 // 4. get方法
            LinkedList.prototype.get = function (position) {
                // 1.越界判断
                if (position < 0 || position >= this.length) return false;

                // 2.获取对应的data
                let current = this.head;
                let index = 0
                while (index++ < position) {
                    current = current.next
                }
                return current.data;
            }
     // 5.indexOf 方法
            LinkedList.prototype.indexOf = function (data) {
                // 1.定义变量
                let current = this.head
                let index = 0;
                // 2.开始查找
                while (current) {
                    if (current.data == data) {
                        return index;
                    }
                    current = current.next;
                    index += 1;
                }
                // 3.找到最后没有找到,返回-1
                return -1
            }

  // 8. remove 方法
            LinkedList.prototype.remove = function (data) {
                // 1.获取data 在列表中的位置
                let position = this.indexOf(data);

                // 根据位置信息 删除节点
                return this.removeAt(position);
            }

            // 9. isEmpty方法
            LinkedList.prototype.isEmpty = function () {
                return this.length == 0;
            }

            // 10. size 方法
            LinkedList.prototype.size = function () {
                return this.length
            }
        }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61