（一）需求
最近开始学习算法，链表是数据结构中蛮经典的一个数据结构。而单链表是基础中的基础。
（二）单链表
1、定义
单链表中的每个结点不仅包含值，还包含链接到下一个结点的引用字段。通过这种方式，单链表将所有结点按顺序组织起来。
文章图片
// Definition for singly-linked list.
public class SinglyListNode {
int val;
SinglyListNode next;
SinglyListNode(int x) { val = x;
}
}在大多数情况下，我们将使用头结点(第一个结点)来表示整个列表。
与数组不同，我们无法在常量时间内访问单链表中的随机元素。 如果我们想要获得第 i 个元素，我们必须从头结点逐个遍历。 我们按索引来访问元素平均要花费 O(N) 时间，其中 N 是链表的长度。2、操作
（1）添加操作
文章图片
- 使用给定值初始化新结点 cur；
- 将 cur 的 next 字段链接到 prev 的下一个结点 next ；
- 将 prev 中的 next 字段链接到 cur 。
文章图片
文章图片
文章图片
3、设计链表
设计链表的实现。您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性：val 和 next。
val 是当前节点的值，next 是指向下一个节点的指针/引用。如果要使用双向链表，则还需要一个属性 prev 以指示链表中的上一个节点。假设链表中的所有节点都是 0-index 的。在链表类中实现这些功能：
- get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。
- addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
- addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。
- addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。
- deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。
var MyLinkedList = function() {
this.head=null
this.length=0
};
/** 获取链表中第 index 个节点的值。如果索引无效，则返回-1。
* @param {number} index
* @return {number}
*/
MyLinkedList.prototype.get = function(index) {
//注意：这里需要有index 等于长度的判断
if(index < 0 || index >= this.length){
return -1
}
let cur=this.head;
let sum=0;
if(index == 0){
return cur.val
}else{
while(sum this.length){
return
}
let node = { val, next: null };
let cur = this.head,
pre,
sum = 0;
if (index === 0) {
return this.addAtHead(val);
//index为0， 头部插入
} else if (index === this.length) {
return this.addAtTail(val);
//index = length，在末尾进行追加
} else {
while (sum <= index - 1) {
//找到index位置的前一个节点
pre = cur;
cur = cur.next;
//下一个节点
sum++;
}
pre.next = node;
node.next = cur;
}
this.length++
};
/** 如果索引 index 有效，则删除链表中的第 index 个节点。
* @param {number} index
* @return {void}
*/
MyLinkedList.prototype.deleteAtIndex = function(index) {
if (index < 0 || index >= this.length) return;
let cur = this.head,
pre,
countIndex = 0;
if (index === 0){
this.head = cur.next
}else{
//let sum=0
//while(sum 【Day|Day 58/100 数据结构链表（1）——单链表】以上
参考链接
Leecode https://leetcode-cn.com/leetb...
写在最后的话
学习路上，常常会懈怠 《有想学技术需要监督的同学嘛~》
https://mp.weixin.qq.com/s/Fy...
