## Introduction

Hello, this article is meant to teach about JavaScript through examples based on the concept of data structures. If, by any reason, you don't want to read or copy the code, I've supplied the
*.js* file to be downloaded.

## Basics

First and foremost, if you are new to JavaScript, you might prefer to start at What you should know about if you are new to JavaScript. It is not the newest of posts, but I would rather refer to something from within CodeProject which
is more likely to stay available.

## Data Structures

According to Wikipedia:

"In computer science, a data structure is a particular way of storing and organizing data in a computer so that it can be used efficiently."

In this article, I will be using some structures which, personally, look like the most basic ones. I know that, through Arrays you can have a greater performance, but the point of this exercise is to practice the understanding of code.

## Types of data structures

*1) Stack*

A stack is a particular data type or collection in which the main operations are the addition of an item, known as push, and removal of it, known as pop.
Stacks implement a LIFO (Last In First Out) structure which means that the last element added to the structure must be the first one to be removed.
It will have the following initial code:

function Stack(){
var top = null;
var count = 0;
this.GetCount = function(){
return count;
}
}

Our stack is going to have four additional methods: `Push(data)`

,
`Pop()`

, `Peek()`

, and `DisplayAll()`

. These will be defined inside the function
`Stack()`

below `this.count`

. Well then, let's start:

`PUSH(DATA)`

:

Description: Pushes (adds) the specified data into the Stack and makes it the top node. It also increases the stack count by 1.

this.Push = function (data) {
var node = {
data: data,
next: null
};
node.next = top;
top = node;
count++;
}

`PEEK()`

:

Description: Peeks at the item from the top of the stack. Returns null if the stack is empty.

this.Peek = function(){
if(top === null){
return null;
}
else{
return top.data;
}
}

`POP()`

:

Description: It looks quite similar to the `PEEK()`

method, but it also removes the top item and decreases the count by 1.

this.Pop = function () {
if (top === null) {
return null;
}
else {
var out = top;
top = top.next;
if (count > 0) {
count--;
}
return out.data;
}
}

`DISPLAYALL()`

:
Description: Displays all data from the stack as an array. To display it as an array was chosen by me because I was not sure on how I would
display it (e.g.,: `console.log`

, `document.write`

, etc..)

this.DisplayAll = function(){
if (top === null) {
return null;
}
else {
var arr = new Array();
var current = top;
for (var i = 0; i < count; i++) {
arr[i] = current.data;
current = current.next;
}
return arr;
}
}

*2) Queue*

Queues are collection that keep objects in a certain order while applying the FIFO (First in First out) format. It is just like a line of people, except that data doesn't cut in it:

function Queue(){
var count = 0;
var head = null;
var tail = null;
this.GetCount = function(){
return count;
}
}

Our queue is also going to have 4 additional methods: `Enqueue(data)`

,
`Dequeue()`

, `PeekAt()`

, and `DisplayAll()`

.

`ENQUEUE(DATA)`

:

Adds an item at the front of the queue. The process is the same as PUSH from stack, but I changed for the sake of the exercise.

this.Enqueue = function (data) {
var node = {
data: data,
next: head
};
if (head === null) {
tail = node;
}
head = node;
count++;
}

`DEQUEUE()`

:

Removes and returns the last item inserted and stored which would be the one at the opposite side of the queue.

this.Dequeue = function () {
if (tail === null) {
return null;
}
else {
var current = head;
var previous = null;
while (current.next) {
previous = current;
current = current.next;
}
previous.next = null;
tail = previous;
if (count > 0) {
count--;
}
else {
head = null;
tail = null;
}
}
}

`DISPLAYALL()`

:
The name says all. It works the same as the method from `stack()`

.

this.DisplayAll = function () {
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;
}
}

`PEEKAT(INDEX)`

:

`PeekAt`

follows the idea of peek, but any item from the queue can be searched and seen.

this.PeekAt = function (index) {
if (index > -1 && index < count) {
var current = head;
for(var i = 0; i < index; i++){
current = current.next;
}
return current.data;
}
else {
return null;
}
}

*3) Linked list*

Linked lists are data structures that are made of groups of nodes which together represent a sequence.
You will notice that both the Queue and the Stack where made using the basic idea of a linked list. However, they have special rule which makes them different in functionality.

function LinkedList() {
var count = 0;
var head = null;
this.GetCount = function(){
return count;
}
}

Our Linked list will have 6 additional methods: `DisplayAll()`

,
`DisplayAt(index)`

, `AddFirst(data)`

, `Add(data, index)`

,
`RemoveFirst()`

, `RemoveAt`

.

this.DisplayAll = function () {
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;
}
}

`DISPLAYAT(INDEX)`

:
Like the previous `PeekAt(index)`

method from Queue display at a specific index or if out of bounds it return null.

this.DisplayAt = function (index) {
if (index > -1 && index < count) {
var current = head;
var i = 0;
while (i++ < index) {
current = current.next;
}
return current.data;
}
else {
return null;
}
}

`ADDFIRST(DATA)`

:
Adds to the front of the list. If you are wondering, front is where the index is 0 and referenced by head.

this.AddFirst = function(data) {
var node = {
data: data,
next: head
};
head = node;
count++;
}

`ADD(DATA,INDEX)`

:

Adds an item to the list at the specified position.

this.Add = function (data, index) {
if (index === 0) {
this.AddFirst(data);
}
else if (index > -1 && index < count) {
var node = {
data: data,
next: null
};
var previous;
var current = head;
var i = 0;
while (i++ < index) {
previous = current;
current = current.next;
}
previous.next = node;
node.next = current;
count++;
}
else {
alert("out of range");
}
}

`REMOVEFIRST()`

:
Removes the first item.

this.RemoveFirst = function () {
if (head === null) {
return null;
}
else {
var out = head;
head = head.next;
if (count > 0) {
count--;
}
return out.data;
}
}

`REMOVEAT(INDEX)`

:

Removes an item from a specific index

this.RemoveAt = function (index) {
if (index === 0) {
return this.RemoveFirst(index);
}
else if (index > -1 && index < count) {
var current = head;
var previous;
var i = 0;
while (i++ < index) {
previous = current;
current = current.next;
}
previous.next = current.next;
count--;
}
else {
return null;
}
return current.data;
}

*4)Deque (Double-ended queue)*

The Double-ended queue is basically like a queue, except that you can add or remove from either side. Now that you are a bit more used to how this works, I would like to make things a bit harder.

function Deque() {
var count = 0;
var head = null;
var tail = null;
this.getHead = function() {
if (head) {
return head.data;
}
return null;
}
this.getTail = function() {
if (tail) {
return tail.data;
}
return null;
}
this.GetCount = function() {
return count;
}
var Node = function(data) {
this.data = data;
this.next = null;
}
}

The deque will have way more methods than the other, with a total of 10, the ones you've seen and: `DisplayHeadToTail()`

, `DisplayTailToHead()`

`AddHead(data)`

, `AddTail(data)`

,`RemoveHead()`

and `RemoveTail()`

.

this.DisplayHeadToTail = function() {
if (head != null) {
var arr = new Array();
var current = head;
while (current) {
arr.push(current.data);
current = current.next;
}
return arr;
} else {
return null;
}
}

`DisplayTailToHead()`

:
Returns the deque data from end to start.

this.DisplayTailToHead = function() {
if (head != null) {
var arr = this.DisplayHeadToTail();
return arr.reverse();
} else {
return null;
}
}

`AddHead(data)`

:

Adds to the front of the deque

this.AddHead = function(data) {
var node = new Node(data);
node.next = head;
head = node;
if (!tail) {
tail = head;
}
count++;
}

`AddTail(data)`

:

Adds to the end of the deque

this.AddTail = function(data) {
var node = new Node(data);
if (!head) {
head = node;
} else {
tail.next = node;
}
tail = node;
count++;
}

`RemoveHead()`

:

Removes at the front of the deque

this.RemoveHead = function() {
if (head) {
if (count === 1) {
head = null;
tail = null;
} else {
head = head.next;
}
count--;
}
}

`RemoveHead()`

:

Removes at the end of the deque

this.RemoveTail = function() {
if (head) {
if (count === 1) {
head = null;
tail = null;
} else {
var current = head;
while (current.next.next) {
current = current.next;
}
tail = current;
tail.next = null;
}
count--;
}
}

*5)Doubly linked list*

The Doubly linked list works by the same principle as the linked list. However, each node contains a reference to both previous and next node, if such node is available. This is particularly useful when there is a need to travel backwards as well as forward.

function DoublyLinkedList(){
var count = 0;
var head = null;
var tail = null;
this.getHead = function() {
if (head) {
return head.data;
}
return null;
}
this.getTail = function() {
if (tail) {
return tail.data;
}
return null;
}
this.GetCount = function() {
return count;
}
var Node = function(data) {
this.data = data;
this.next = null;
this.previous = null;
}
}

Our Doubly Linked list will be the final challenge and the longest one with an addtional 9 methods: `DisplayAll()`

, `DisplayAllBackwards()`

`DisplayAt(index)`

, `AddFirst(data)`

,`AddLast(data)`

, `Add(data, index)`

,
`RemoveFirst()`

, `RemoveFirst()`

, `RemoveAt`

.

this.DisplayAll = function () {
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;
}
}

`DISPLAYALLBACKWARDS()`

:
Returns an array with the data from tail to head or if empty it returns null.

Take a close look at this method and think how hard would be to implement it in a normal linked list

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;
}
}

`DISPLAYAT(INDEX)`

:

Works the same way as with linked list.

this.DisplayAt = function (index) {
if (index > -1 && index < count) {
var current = head;
var i = 0;
while (i++ < index) {
current = current.next;
}
return current.data;
}
else {
return null;
}
}

`ADDFIRST(DATA)`

:
Adds to the front of the doubly linked list.

this.AddFirst = function (data) {
var node = new Node(data);
node.next = head;
head = node;
if (count === 0) {
tail = head;
}
else {
head.next.previous = head;
}
count++;
}

`ADDLAST(DATA)`

:
Adds to the end of the doubly linked list.

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(DATA,INDEX)`

:

Adds an item at the specified position. Tip: Draw the process if necessary, it is not as simple as you might think.

this.Add = function (data, index) {
if (index > 0 && index < count) {
var node = new Node(data);
var current = head;
var i = 0;
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);
}
}

`REMOVEFIRST()`

:
Removes the first item.

this.RemoveFirst = function () {
if (head) {
head = head.next;
count--;
if (count === 0) {
tail = null;
}
else {
head.previous = null;
}
}
}

`REMOVELAST()`

:
Removes the last item.

this.RemoveLast = function () {
if (head) {
if (count === 1) {
head = null;
tail = null;
}
else {
tail.previous.next = null;
tail = tail.previous;
}
count--;
}
}

`REMOVEAT(INDEX)`

:

Removes an item from a specific index

this.RemoveAt = function (index) {
if (index > 0 && index < count-1) {
var current = head;
var i = 0;
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();
}
}

### Notes

This has been a great experience, I remember when I created those structures and how much was learned from it.

Once again, it is possible to get those structures done better and I encourage all readers to give it a shot. If you don't know where to start, here are some hints:

- Try to make a standard. I have deliberately changed some of the methods just to show it could be done differently
- Change something. Why should only the remove return the value? Can you make everything return true or false depending on the success of the execution?
- Can you do it but in a completely different way? I challenge you to post those 3 data structures using a different algorithm. Arrays for list don't count :P
- Try to implement the stack and queue as with nodes that have previous and next references.
- Try to list all items from the linked list from tail to back.

As you guys may have noticed, English is not my first language, so any and every correction is welcome. The same for correction on the code.

Hopefully I will be continuing this with harder data structures, if my job allows.

## Source