JavaScript 数据结构
4.91/5 (55投票s)
关于基本数据结构和 JavaScript 的教程。
引言
大家好，本文旨在通过基于数据结构概念的示例来教授 JavaScript。如果出于任何原因您不想阅读或复制代码，我已经提供了 .js 文件供下载。
基础
首先，如果您是 JavaScript 新手，您可能更喜欢从 JavaScript 新手应了解的内容 开始。这不是最新的文章，但我宁愿引用 CodeProject 内部的内容，这样更有可能保持可用。
数据结构
根据维基百科
"在计算机科学中，数据结构是一种在计算机中存储和组织数据的特定方式，以便可以高效地使用它们。"
在本文中，我将使用一些在我看来是最基本的结构。我知道通过数组可以获得更好的性能，但这个练习的目的是练习对代码的理解。
数据结构类型
1) 堆栈
堆栈是一种特殊的数据类型或集合，其中主要操作是添加项目（称为 push）和删除项目（称为 pop）。堆栈实现 LIFO（后进先出）结构，这意味着最后添加到结构中的元素必须是第一个被移除的元素。它将具有以下初始代码：
function Stack(){
var top = null;
var count = 0;
//Returns the number of items in the queue
this.GetCount = function(){
return count;
}
/* Methods */
}
我们的堆栈将有四个附加方法：Push(data)、Pop()、Peek() 和 DisplayAll()。这些将在 this.count 下方的 Stack() 函数内部定义。那么，让我们开始吧
推送 (Push)
描述：将指定数据推入（添加）到堆栈中并使其成为顶部节点。它还将堆栈计数增加 1。
this.Push = function (data) {
//Creates a node containing the data and a reference to the next item, if any.
var node = {
data: data,
next: null
};
//links the current node to the top node. If the stack is empty it will have null as reference
node.next = top;
//makes the current node as the top node.
top = node;
//Increases the count
count++;
}
窥视
描述：查看堆栈顶部的项目。如果堆栈为空，则返回 null。
this.Peek = function(){
//If there are no items, returns null. (avoid error)
if(top === null){
return null;
}
else{
return top.data;
}
}
Pop
描述：它看起来与 PEEK() 方法非常相似，但它还会删除顶部项目并将计数减 1。
this.Pop = function () {
//If there are no items, returns null. (avoid error)
if (top === null) {
return null;
}
else {
//assigns top to a temp variable
var out = top;
//makes the TOP as the next in line
top = top.next;
//there still are items on the stack
if (count > 0) {
count--;
}
//returns the value that was removed
return out.data;
}
}
显示所有
描述：将堆栈中的所有数据显示为数组。我选择将其显示为数组，因为我不确定如何显示它（例如：console.log、document.write 等）。
this.DisplayAll = function(){
if (top === null) {
return null;
}
else {
//instantiate an array
var arr = new Array();
//creates a node to move through the stack
var current = top;
//moves through the stack until it reaches the bottom item
for (var i = 0; i < count; i++) {
//assigns the data to the array
arr[i] = current.data;
//advances one step
current = current.next;
}
//returns the array
return arr;
}
}
PUSH(数据):PEEK():POP():DISPLAYALL():
2) 队列
队列是按特定顺序保存对象的集合，同时应用 FIFO（先进先出）格式。它就像排队的人一样，只是数据不会插队。
function Queue(){
var count = 0;
//Yes, I don't use back and front.
var head = null;
var tail = null;
//Returns the number of items in the queue
this.GetCount = function(){
return count;
}
/* Methods */
}
我们的队列也将有 4 个附加方法：Enqueue(data)、Dequeue()、PeekAt() 和 DisplayAll()。
Enqueue
描述：在队列前面添加一个项目。这个过程与堆栈的 PUSH 相同，但我为了练习而更改了它。
this.Enqueue = function (data) {
//Creates a node with the data
var node = {
data: data,
//next points to value straight way. If head is null, it won't be a problem
next: head
};
//if it is the first item, then the head is also the tail
if (head === null) {
tail = node;
}
//defines the node as the new head
head = node;
//increases the count
count++;
}
出队
描述：移除并返回最后插入和存储的项目，该项目位于队列的另一侧。
this.Dequeue = function () {
//if queue is empty, returns null
if (count === 0) {
return;
}
else {
var current = head;
var previous = null;
//while there is a next, it will advance the queue.
//the idea is to have "current" at the end and "previous" as the one before last
while (current.next) {
previous = current;
current = current.next;
}
//if there is more than 1 item,
//Removes the tail and decreases count by 1.
if (count > 1) {
//Remove the reference to the last one.
previous.next = null;
//makes tail point to the previous node.
tail = previous;
}
//resets the queue
else {
head = null;
tail = null;
}
count--;
}
}
显示所有
描述：名称说明了一切。它与 stack() 中的方法功能相同。
this.DisplayAll = function () {
//
//I will leave the analysis to you.
//
if (head === null) {
return null;
}
else {
var arr = new Array();
var current = head;
for (var i = 0; i < count; i++) {
arr[i] = current.data;
current = current.next;
}
return arr;
}
}
查看
描述：遵循 peek 的思想，但可以搜索和查看队列中的任何项目。
this.PeekAt = function (index) {
//anything smaller than 0 and equal or greater than count is not at the queue
if (index > -1 && index < count) {
var current = head;
//Navigates through the queue to find the item
for(var i = 0; i < index; i++){
current = current.next;
}
return current.data;
}
//an index out of the bounds of the queue was chosen.
else {
return null;
}
}
入队(数据):出队():DISPLAYALL():PEEKAT(索引):
3) 链表
链表是由节点组构成的数据结构，这些节点组共同表示一个序列。您会注意到队列和堆栈都是使用链表的基本思想构建的。但是，它们具有特殊的规则，使其在功能上有所不同。
function LinkedList() {
var count = 0;
var head = null;
this.GetCount = function(){
return count;
}
// Methods go here
}
我们的链表将有 6 个附加方法：DisplayAll()、DisplayAt(index)、AddFirst(data)、Add(data, index)、RemoveFirst()、RemoveAt。
显示所有
描述：名称说明了一切。返回一个包含数据的数组，如果为空则返回 null。
this.DisplayAll = function () {
//if is empty
if (head === null) {
return null;
}
else {
//if not, runs trough the list and place it in an array.
var arr = new Array();
var current = head;
for (var i = 0; i < count; i++) {
arr[i] = current.data;
current = current.next;
}
return arr;
}
}
在...显示
描述：与队列中的上一个 PeekAt(index) 方法类似，在特定索引处显示，如果超出范围则返回 null。
this.DisplayAt = function (index) {
//check for out-of-bounds values
if (index > -1 && index < count) {
var current = head;
var i = 0;
//this was not me, it is from nczonline(see source).
//It is a different way to implelement from the FOR we've been using
//and I wanted everyone have the chance to know it.
while (i++ < index) {
current = current.next;
}
return current.data;
}
else {
return null;
}
}
添加第一个
描述：添加到列表的开头。如果您想知道，开头是指索引为 0 并且由头节点引用的位置。
this.AddFirst = function(data) {
//creates a new node
var node = {
data: data,
next: head
};
head = node;
count++;
}
Add
描述：在指定位置向列表中添加一个项目。
this.Add = function (data, index) {
//if the chosen index is 0 do the AddFirst(data) method.
if (index === 0) {
this.AddFirst(data);
}
//check for out-of-bounds values
else if (index > -1 && index < count) {
var node = {
data: data,
next: null
};
var previous;
var current = head;
var i = 0;
//find the right location
while (i++ < index) {
previous = current;
current = current.next;
}
previous.next = node;
node.next = current;
count++;
}
else {
alert("out of range");
}
}
移除第一个
描述：移除第一个项目。
this.RemoveFirst = function () {
//if no items on the list, returns null
if (head === null) {
return null;
}
else {
var out = head;
head = head.next;
if (count > 0) {
count--;
}
return out.data;
}
}
移除于
描述：从特定索引移除一个项目
this.RemoveAt = function (index) {
if (index === 0) {
return this.RemoveFirst(index);
}
//check for out-of-bounds values
else if (index > -1 && index < count) {
var current = head;
var previous;
var i = 0;
//find the right location
while (i++ < index) {
previous = current;
current = current.next;
}
//skip over the item to remove
previous.next = current.next;
//decrement the length
count--;
}
else {
return null;
}
//return the value
return current.data;
}
DISPLAYALL():显示于(索引):添加第一个(数据):添加(数据,索引):移除第一个():移除于(索引):
4) 双端队列 (Double-ended queue)
双端队列基本上像一个队列，只是你可以从两端添加或移除。既然您对它的工作原理更熟悉了，我想让事情变得更难一些。
function Deque() {
var count = 0;
var head = null;
var tail = null;
//Allows to view the value stored on Head
this.getHead = function() {
if (head) {
return head.data;
}
return null;
}
//Allows to view the value stored on Tail
this.getTail = function() {
if (tail) {
return tail.data;
}
return null;
}
//Returns the number of items
this.GetCount = function() {
return count;
}
//Lets define the node structure outside of each method.
//This way it will need to be done only once
var Node = function(data) {
this.data = data;
this.next = null;
}
//Methods go here
}
双端队列将比其他队列拥有更多的方法，总共有 10 个，包括您已经看到的方法和：DisplayHeadToTail()、DisplayTailToHead()、AddHead(data)、AddTail(data)、RemoveHead() 和 RemoveTail()。
从头到尾显示
描述：返回一个包含数据的数组，如果为空则返回 null。
this.DisplayHeadToTail = function() {
if (head != null) {
var arr = new Array();
var current = head;
//while there is a current
while (current) {
//ATTENTION: To those new to javascript, have a look. Can you guess what this method does?
arr.push(current.data);
current = current.next;
}
return arr;
} else {
return null;
}
}
从尾到头显示
描述：从尾到头返回双端队列数据（与之前相反）。
this.DisplayTailToHead = function() {
if (head != null) {
//call DisplayHeadToTail() and reverse it.
var arr = this.DisplayHeadToTail();
//This is one of the many great methods from javascript.
return arr.reverse();
} else {
return null;
}
}
添加头
描述：添加到双端队列的前面（头）
this.AddHead = function(data) {
//As you can see, now we only need to declare a new node
var node = new Node(data);
node.next = head;
head = node;
//if the list was empty
if (!tail) {
tail = head;
}
count++;
}
添加尾
描述：添加到双端队列的末尾（尾）
this.AddTail = function(data) {
var node = new Node(data);
//if the list was empty
if (!head) {
head = node;
} else {
tail.next = node;
}
tail = node;
count++;
}
移除头
描述：从双端队列的前面（头）移除
this.RemoveHead = function() {
if (head) {
//If it's the last item
if (count === 1) {
head = null;
tail = null;
} else {
head = head.next;
}
count--;
}
}
移除尾
从双端队列的末尾（尾）移除
this.RemoveTail = function() {
if (head) {
//If it's the last item
if (count === 1) {
head = null;
tail = null;
} else {
var current = head;
//we need to go as far as the 2 before last
while (current.next.next) {
current = current.next;
}
tail = current;
tail.next = null;
}
count--;
}
}
DisplayHeadToTail():DisplayTailToHead():AddHead(data):AddTail(data):RemoveHead():RemoveHead():
5) 双向链表
双向链表的工作原理与链表相同。但是，每个节点都包含对前一个节点和下一个节点的引用（如果存在）。当需要向后和向前遍历时，这特别有用。
function DoublyLinkedList(){
var count = 0;
var head = null;
var tail = null;
//Allows to view the value stored on Head
this.getHead = function() {
if (head) {
return head.data;
}
return null;
}
//Allows to view the value stored on Tail
this.getTail = function() {
if (tail) {
return tail.data;
}
return null;
}
//Returns the number of items
this.GetCount = function() {
return count;
}
//Defines the node
var Node = function(data) {
this.data = data;
this.next = null;
this.previous = null;
}
// Methods go here
}
我们的双向链表将是最终的挑战，也是最长的一个，增加了 9 个方法：DisplayAll()、DisplayAllBackwards()、DisplayAt(index)、AddFirst(data)、AddLast(data)、Add(data, index)、RemoveFirst()、RemoveFirst()、RemoveAt。
显示所有
描述：返回一个包含数据的数组，如果为空则返回 null。
this.DisplayAll = function () {
//Most of the time, head won't be null, so lets start by that this time
if (head) {
var arr = new Array();
var current = head;
for (var i = 0; i < count; i++) {
arr[i] = current.data;
current = current.next;
}
return arr;
}
else {
return null;
}
}
倒序显示所有
描述：返回一个包含从尾到头数据的数组，如果为空则返回 null。
仔细看看这个方法，想想在普通链表中实现它会有多难。
this.DisplayAllBackwards = function(){
if (head) {
var arr = new Array();
var current = tail;
for (var i = 0; i < count; i++) {
arr[i] = current.data;
current = current.previous;
}
return arr;
}
else {
return null;
}
}
在...显示
描述：与链表的工作方式相同。
this.DisplayAt = function (index) {
//check for out-of-bounds values
if (index > -1 && index < count) {
var current = head;
var i = 0;
//this was not me, it is from nczonline(see source).
//It is a different way to implelement from the FOR we've been using
//and I wanted everyone have the chance to know it.
while (i++ < index) {
current = current.next;
}
return current.data;
}
else {
return null;
}
}
添加第一个
描述：添加到双向链表的开头。
this.AddFirst = function (data) {
//creates a new node
var node = new Node(data);
node.next = head;
head = node;
//if the list was empty
if (count === 0) {
tail = head;
}
else {
//Don't forget about the previous node. It also needs to be referenced.
head.next.previous = head;
}
count++;
}
添加最后一个
描述：添加到双向链表的末尾。
this.AddLast = function (data) {
var node = new Node(data);
node.previous = tail;
if (count === 0) {
head = node;
}
else {
tail.next = node;
}
tail = node;
count++;
}
Add
描述：在指定位置添加一个项目。提示：如有必要，画出过程图，它不像你想象的那么简单。
this.Add = function (data, index) {
//check for out-of-bounds values
if (index > 0 && index < count) {
var node = new Node(data);
var current = head;
var i = 0;
//find the right location
while (i++ < index) {
current = current.next;
}
current.previous.next = node;
node.next = current;
node.previous = current.previous;
current.previous = node;
count++;
}
else if (index < 1) {
this.AddFirst(data);
}
else {
this.AddLast(data);
}
}
移除第一个
描述：移除第一个项目。
this.RemoveFirst = function () {
if (head) {
head = head.next;
count--;
//there was only one item
if (count === 0) {
tail = null;
}
else {
//Don't forget about the previous node. It also needs the reference set to null.
head.previous = null;
}
}
}
移除最后一个
描述：移除最后一个项目。
this.RemoveLast = function () {
if (head) {
//there is only one item
if (count === 1) {
head = null;
tail = null;
}
else {
tail.previous.next = null;
tail = tail.previous;
}
count--;
}
}
移除于
描述：从特定索引移除一个项目
this.RemoveAt = function (index) {
//check for out-of-bounds values
if (index > 0 && index < count-1) {
var current = head;
var i = 0;
//find the right location
while (i++ < index) {
current = current.next;
}
current.previous.next = current.next;
current.next.previous = current.previous;
count--;
}
else if (index < 1) {
this.RemoveFirst();
}
else {
this.RemoveLast();
}
}
DISPLAYALL():显示所有倒序():显示于(索引):添加第一个(数据):添加最后一个(数据):添加(数据,索引):移除第一个():移除最后一个():移除于(索引):
注释
这是一次很棒的经历，我记得我创建这些结构以及从中学习到的东西。
再次强调，可以更好地完成这些结构，我鼓励所有读者尝试一下。如果您不知道从何开始，这里有一些提示。
- 尝试制定一个标准。我故意更改了一些方法，只是为了表明可以以不同的方式完成。
- 改变一些东西。为什么只有移除返回价值？你能让所有东西都根据执行的成功返回 true 或 false 吗？
- 你能用完全不同的方式做到吗？我挑战你使用不同的算法发布这 3 种数据结构。列表的数组不算 :P
- 尝试将堆栈和队列实现为具有前一个和下一个引用的节点。
- 尝试从链表的尾部到头部列出所有项目。
正如大家可能已经注意到的，英语不是我的第一语言，因此欢迎任何和所有的更正。代码的更正也一样。
如果我的工作允许，我希望能继续研究更难的数据结构。
来源
- http://www.nczonline.net/blog/2009/04/13/computer-science-in-javascript-linked-list/
- http://www.codecademy.com/
- http://en.wikipedia.org/wiki/Linked_list
- http://en.wikipedia.org/wiki/Queue_(abstract_data_type)
- http://en.wikipedia.org/wiki/Stack_(abstract_data_type)
- http://en.wikipedia.org/wiki/Doubly_linked_list