大佬说：链表不过是对象之间多了一层引用关系罢了。很多东西重要的是本质而不是如何实现
链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
链表的好处在于，添加或者移除元素的时候不需要移动其他的元素。
想要访问链表中间的一个元素，需要从头迭代列表直至找到所需要的元素。
实现如下
function LinkedList() {
//定义结点
let Node = function (element) {
this.element = element;
this.next = null;
};
let length = 0;
let head = null;
//向列表尾部添加一个新项
this.append = function (element) {
let node = new Node(element),current;
if (head === null){
head = node;
} else {
current = head;
//循环列表，直到找到最后一项
while(current.next){
current = current.next;
}
//找到最后一项，将其next赋值为node，建立连接
current.next = node;
}
length++;
};
//向列表特定位置插入一个新的项,position位置
this.insert = function (position, element) {
//检查越界值
if (position >= 0 && position <= length){
let node = new Node(element),
current = head,
previous,
index = 0;//index作为标志
if(position === 0){
//在第一个位置添加
node.next = head;
head = node;
}else{
while (index++ < position){
previous = current;
current = current.next;
}
node.next = current;
previous.next = node;
}
length++;
return true;
} else {
return false;
}
}
//从列表中移除一项
this.remove = function (element) {
let index = this.indexOf(element);
return this.removeAt(index);
}
//从列表特定位置移除一项
this.removeAt = function (position) {
//判断越界值
if (position >= 0 && position < length){
let current = head,
previous,
index = 0;
//移除第一项
if (position === 0) {
head = current.next;
} else {
while (index++ < position) {
previous = current;
current = current.next;
}
previous.next = current.next;
}
length--;
return current.element;
} else {
return null;
}
}
//返回元素在列表中的索引，没有该元素则返回-1
this.indexOf = function (element) {
let current = head,
index = 0;
while (current) {
if (element === current.element){
return index;
}
index++;
current = current.next;
}
return -1;
}
//判断链表是否包含任何元素，链表长度>1则返回false，否则返回true
this.isEmpty = function () {
return length === 0;
}
//返回链表包含的元素个数
this.size = function () {
return length;
}
//获取链表的第一个元素
this.getHeader = function () {
return head;
}
//重写toString方法，只输出元素的值
this.toString = function () {
let current = head,
string = '';
while (current) {
string += current.element + (current.next ? 'n' : '');
current = current.next;
}
return string;
}
}
var linkedList = new LinkedList();
console.log(linkedList.isEmpty());
linkedList.append(123);
linkedList.append(1);
linkedList.append(22);
linkedList.append(4);
console.log(linkedList.isEmpty());
console.log(linkedList.toString());
console.log(linkedList.remove(22));
console.log(linkedList.size());
linkedList.insert(3,'555');
console.log(linkedList.toString());
双向链表
function DoublyLinkedList() {
//定义结点
let Node = function (element) {
this.element = element;
this.next = null;
this.prev = null;
};
let length = 0;
let head = null;//头
let tail = null;//尾
//向列表尾部添加一个新项
this.append = function (element) {
let node = new Node(element),current;
if (head === null){
head = node;
tail = node;
} else {
//找到最后一项,将其next赋值为node，建立连接
current = tail;
current.next = node;
node.prev = current;
tail = node;
}
length++;//更新长度
};
//向列表特定位置插入一个新的项,position位置
this.insert = function (position, element) {
//检查越界值
if (position >= 0 && position <= length){
let node = new Node(element),
current = head,
previous,
index = 0;//index作为标志
if(position === 0){
//在第一个位置添加,双向链表，所以存在链表为空或者不为空两种情况
if(!head){
head = node;
tail = node;
}else{
node.next = current;
current.prev = node;
head = node;
}
}else if(position === length){
//在尾部插入
current = tail;
current.next = node;
node.prev = current;
tail = node;
}else{
while (index++ < position){
previous = current;
current = current.next;
}
node.next = current;
previous.next = node;
current.prev = node;
node.prev = previous;
}
length++;
return true;
} else {
return false;
}
}
//从列表中移除一项
this.remove = function (element) {
let index = this.indexOf(element);
return this.removeAt(index);
}
//从列表特定位置移除一项
this.removeAt = function (position) {
//判断越界值
if (position >= 0 && position < length){
let current = head,
previous,
index = 0;
//移除第一项
if (position === 0) {
head = current.next;
//如果只有一项，需要更新tail
if(length === 1){
tail = null;
}else{
head.prev = null;
}
} else if (position === length) {
current = tail;
tail = current.prev;
tail.next = null;
}else{
while (index++ < position) {
previous = current;
current = current.next;
}
previous.next = current.next;
current.next.prev = previous;
}
length--;
return current.element;
} else {
return null;
}
}
//返回元素在列表中的索引，没有该元素则返回-1
this.indexOf = function (element) {
let current = head,
index = 0;
while (current) {
if (element === current.element){
return index;
}
index++;
current = current.next;
}
return -1;
}
//判断链表是否包含任何元素，链表长度>1则返回false，否则返回true
this.isEmpty = function () {
return length === 0;
}
//返回链表包含的元素个数
this.size = function () {
return length;
}
//获取链表的第一个元素
this.getHeader = function () {
return head;
}
//重写toString方法，只输出元素的值
this.toString = function () {
let current = head,
string = '';
while (current) {
string += current.element + (current.next ? 'n' : '');
current = current.next;
}
return string;
}
}
有兴趣可以加入Nodejs交流群，和大佬们一起成长！！！
群号：348108867
图片.png
