链表_链表封装

53 阅读 0 评论 35 点赞

我是靠谱客的博主斯文背包，最近开发中收集的这篇文章主要介绍链表_链表封装，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

链表结构本身就是一种可以代替数组的结构，所以它的操作与数组的操作非常类似。

与数组比较，它们都可以存储一系列的元素，但是实现的机制完全不同。

数组有很多缺点：

数组需要申请一段连续的内存空间，并且大小是固定的（大多数编程语言），所以在数组增加元素时需要扩容。（一般情况下是申请一个更大的连续内存空间，比如2倍，再将元素复制过去）
在数组的中间或末尾插入元素成本很高，因为它内部需要改变插入位置后面的所有元素的位置。

数组的优点也很显然：

可以通过下标直接查找元素。

链表相对于数组来说，缺点在于：

查找元素时需要从第一个依次往后查找。

链表的优点：

链表创建时在内存中不必是连续的内存空间。
链表在插入删除操作时，时间复杂度可以到达O(1)，相对于数组效率高很多。

链表的每个元素由元素节点本身和下一个元素节点的引用组成。
链表必须有一个head属性用来指向第一个元素节点。

列表的常用方法有：

append
insert
get
indexOf
update
removeAt
remove
isEmpty
size
toString

接下来我们先实现用 JavaScript 封装一个链表：

function LinkedList() {
function Node(data) {
this.data = data;
this.next = null;
}
// 属性
this.head = null;
this.length = 0;
// 常见方法
// 1. append(element)
LinkedList.prototype.append = function(data) {
// 创建输入的元素对象
let newNode = new Node(data);
// 当链表中本来就没有元素时，使 head 指向新的节点 newNode
if (this.length == 0) {
this.head = newNode;
} else {
// 当链表中本来就有元素的时候，我们需要找到最后一个元素
var current = this.head;
while (current.next) {
current = current.next;
}
// 找到最后一个元素后，让其 next 指向新的节点
current.next = newNode;
}
// 最后修改 length 属性
this.length ++;
}
// 2. insert(position, element)
LinkedList.prototype.insert = function(position, data) {
// 如果 position 超过边界，直接返回 false
if (position < 0 || position > this.length) {
return false;
}
let newNode = new Node(data);
// 判断插入的位置是不是第一个
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 ++;
return true;
}
// 3. get(position)
LinkedList.prototype.get = function(position) {
// 越界判断
if (position < 0 || position >= this.length) {
return false;
}
// 获取数据
let current = this.head;
let index = 0;
while (index ++ < position) {
current = current.next;
}
return current.data;
}
// 4. indexOf(element)
LinkedList.prototype.indexOf = function(data) {
let current = this.head;
let index = 0;
// 开始查找
while (current) {
if (current.data == data) {
return index;
}
current = current.next;
index ++;
}
return -1;
}
// 5. update(position, newData)
LinkedList.prototype.update = function(position, newData) {
// 越界判断
if (position < 0 || position >= this.length) {
return false;
}
// 查找正确的节点
let current = this.head;
let index = 0;
while (index ++ < position) {
current = current.next;
}
current.data = newData;
return true;
}
// 6. removeAt(position)
LinkedList.prototype.removeAt = function(position) {
// 越界判断
if (position < 0 || position >= this.length) {
return false;
}
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 --;
return current.data;
}
// 7. remove(element)
LinkedList.prototype.remove = function(data) {
// 找出节点位置
let position = this.indexOf(data);
// 根据位置删除元素
return this.removeAt(position);
}
// 8. isEmpty
LinkedList.prototype.isEmpty = function() {
return this.length == 0;
}
// 9. size()
LinkedList.prototype.size = function() {
return this.length;
}
// 10. toString()
LinkedList.prototype.toString = function() {
let current = this.head;
let resultString = '';
// 循坏获取每一个节点
while (current) {
resultString += current.data + ' ';
current = current.next;
}
return resultString;
}
}