@[toc]
What is a singly linked list?
A singly linked list is a chained access structure that stores data elements in a linear list in a set of arbitrarily addressed storage cells. The data in the linked list is represented by nodes, and the composition of each node is:Element (image of the data element) + pointer (indicating where the subsequent element is stored), the element is the storage unit that stores data, and the pointer is the address data that connects each node.
Two, single linked list encapsulation
// Encapsulate the linked list class
function LinkedList() {
// Inner class: node class
function Node(data) {
this.data=data;
this.next=null;
}
/ / property
this.head=null;
this.length=0;
}
Copy the codeThree, single linked list common operations (add, delete, change and check)
- Append (Element) : Adds a new item to the end of the list
- Insert (position,element): Inserts a new item into a specific position in the list
- Get (position): Obtains the element at the corresponding position
- IndexOf (element): returns the indexOf an element on a list. Returns -1 if the element is not on the list
- Updata (position, element) : Updates an element
- RemoveAt (position) : Removes an item from a specific position in the list (by position)
- remove(element); Remove an item from the list (by element)
- IsEmpty (): Returns true if the list contains no elements, false if the list length is greater than zero.
- Size (): Returns the number of elements in the list.
- The tostring () : output
3.1 AppEnd (Element) : Adds a new item to the end of the list
Steps:
1. Create a newNode (newNode)
2. Check whether the first node is added
2.1 is the first node
2.2 is not the first node
2.2.1 Finding the Last Node (Using the Current cursor)
2.2.2 Point next of the last node to the new node
LinkedList.prototype.append=function(data){
1. Create a node
var newNode=new Node(data);
// 2. Check whether the first node is added
if (this.length==0) {
// 2.1 is the first node
this.head=newNode;
} else {
// 2.2 is not the first node
var current=this.head;
2.2.1 Finding the last node
while (current.next) {
current=current.next
}
// 2.2.2 Point next of the last node to the new node
current.next=newNode;
}
this.length+=1;
}
Copy the code3.2 Insert (position, Element): Inserts a new item into a specific position in the linked list
Steps:
1. Perform boundary-crossing judgment on position
2. Create a newNode based on data
3. Check whether the inserted position is the first one
3.1 Figure (Inserted first)
3.2 Figure (insert in other bits)
3.1 :(inserted first)
3.2 (Insert in other Bits)
/* insert() : insert */
LinkedList.prototype.insert = function (position, data) {
// 1. Judge position to be out of bounds
if (position < 0 && position > this.length) {
return false
}
// 2. Create newNode based on data
var newNode = new Node(data);
// 3. Check whether the insert position is the first one
if (position == 0) {
// 3.1 Figure (insert first)
newNode.next =this.head
this.head = newNode;
} else {
// 3.2 Figure (insert other bits)
var index=0;
var current=this.head;
var previous=null;
// Stop index at position
while (index<position) {
previous=current;
current=current.next;
index+=1;
}
/ / understand?
newNode.next=current;
previous.next=newNode;
}
this.length+=1;
return true;
}
Copy the code3.3 GET (position): Obtains the element at the corresponding position
Steps:
1. Perform boundary-crossing judgment on position
2. To obtain the data
/* get(position): get the corresponding element */
LinkedList.prototype.get=function(position){
// Cross the line
if (position < 0 || position >=this.length) {
return null;
}
// Get the desired data
var index=0;
var current=this.head;
while (index<position) {
current=current.next;
index++;
}
return current.data;
}
Copy the code3.4 indexOf(element): returns the indexOf the element in the list. Returns -1 if the element is not on the list
Steps:
Cycle, compare
LinkedList.prototype.indexOf=function(element){
var index=0;
var current=this.head;
console.log(this.length);
while (index<this.length) {/ / or while (current)
if (current.data==element) {
return index;
}
current=current.next;
index+=1
}
return -1;
}
Copy the code3.5 Undata (position, Element) : Changes the position of an element
Steps:
1. Crossing the line
2. Locate the correct node
3. Change the data of the node in position to newData
LinkedList.prototype.updata=function(position,element){
// Perform an out-of-bounds judgment on position
if (position<0||position>=this.length) {
return false;
}
var current=this.head;
var index=0;
// Find the correct node
while (index<position) {
current=current.next;
index+=1;
}
// Change the node data in position to newData
current.data=element;
return true;
}
Copy the code3.6 removeAt (Position) : Removes an item from a specific position in the list (by position)
steps
1. Perform boundary-crossing judgment on position
2. Determine the node type to be deleted (Position is 0)
3. Make the previous next point to current next
LinkedList.prototype.removeAt = function (position) {
//1. Judge position to be out of bounds
if (position < 0 || position >= this.length) {
return false;
}
// 2. Determine the type of the node to be deleted
if (position == 0) {
this.head = this.head.next;
} else {
var current = this.head;
var index = 0;
var previous = null;
while (index < position) {
previous = current;
current = current.next;
index++;
}
//3. Let the previous next point to current next
previous.next = current.next;
current.next = null;
}
this.length-=1;
return true;
}
Copy the code3.7 remove (element); Remove an item from the list (by element)
Steps :(can be used directly with removeAt and indexOf)
To obtain position
Remove elements
LinkedList.prototype.remove=function(element){
var index=0;
var current=this.head;
var previous=null;
while (current) {
if (current.data==element) {
if (index==0) {
this.head=this.head.next;
} else {
previous.next=current.next;
}
this.length-=1;
return true;
}
previous=current;
current=current.next;
index+=1;
}
return -1;
}
Copy the code3.8 isEmpty () : found empty
LinkedList.prototype.isEmpty = function () {
return this.length==0;
}
Copy the code3.9 size(): Returns the number of elements in the list.
LinkedList.prototype.size = function () {
return this.length;
}
Copy the code3.10 the tostring () : output
Steps:
1. Define a cursor
2. Circular acquisition
LinkedList.prototype.tostring=function(){
// Define the cursor
var currrent=this.head;
var stringsub="";
// loop fetch
while(currrent){
stringsub+=currrent.data+"";
currrent=currrent.next;
}
return stringsub;
}
Copy the code4. The source code
<! DOCTYPEhtml>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta name="viewport" content="Width = device - width, initial - scale = 1.0">
<title>One-way list</title>
</head>
<body>
</body>
<script>
// Encapsulate the linked list class
function LinkedList() {
// Inner class: node class
function Node(data) {
this.data = data;
this.next = null;
}
/ / property
this.head = null;
this.length = 0;
/* appEnd (element) : Adds a new item */ to the end of the list
LinkedList.prototype.append = function (data) {
1. Create a node
var newNode = new Node(data);
// 2. Check whether the first node is added
if (this.length == 0) {
// 2.1 is the first node
this.head = newNode;
} else {
// 2.2 is not the first node
var current = this.head;
2.2.1 Finding the last node
while (current.next) {
current = current.next
}
// 2.2.2 Point next of the last node to the new node
current.next = newNode;
}
this.length += 1;
}
/* tostring(): outputs */
LinkedList.prototype.tostring = function () {
// Define the cursor
var currrent = this.head;
var stringsub = "";
// loop fetch
while (currrent) {
stringsub += currrent.data + "";
currrent = currrent.next;
}
return stringsub;
}
/* insert() : insert */
LinkedList.prototype.insert = function (position, data) {
// 1. Judge position to be out of bounds
if (position < 0 && position > this.length) {
return false
}
// 2. Create newNode based on data
var newNode = new Node(data);
// 3. Check whether the insert position is the first one
if (position == 0) {
// 3.1 Figure (insert first)
newNode.next = this.head
this.head = newNode;
} else {
// 3.2 Figure (insert other bits)
var index = 0;
var current = this.head;
var previous = null;
// Stop index at position
while (index < position) {
previous = current;
current = current.next;
index += 1;
}
/ / understand?
newNode.next = current;
previous.next = newNode;
}
this.length += 1;
return true;
}
/* get(position): get the corresponding element */
LinkedList.prototype.get = function (position) {
// Cross the line
if (position < 0 || position >= this.length) {
return null;
}
// Get the desired data
var index = 0;
var current = this.head;
while (index < position) {
current = current.next;
index++;
}
return current.data;
}
/* indexOf(element): returns the indexOf the element on the list. Returns -1 */ if the element is not on the list
LinkedList.prototype.indexOf = function (element) {
var index = 0;
var current = this.head;
console.log(this.length);
while (index < this.length) {/ / or while (current)
if (current.data == element) {
return index;
}
current = current.next;
index += 1
}
return -1;
}
/* undata (position, element) : changes the position of an element */
LinkedList.prototype.updata = function (position, element) {
// Perform an out-of-bounds judgment on position
if (position < 0 || position >= this.length) {
return false;
}
var current = this.head;
var index = 0;
// Find the correct node
while (index < position) {
current = current.next;
index += 1;
}
// Change the node data in position to newData
current.data = element;
return true;
}
/*removeAt (position) : Removes an item from a specific position in the list (by position) */
LinkedList.prototype.removeAt = function (position) {
//1. Judge position to be out of bounds
if (position < 0 || position >= this.length) {
return false;
}
// 2. Determine the type of the node to be deleted
if (position == 0) {
this.head = this.head.next;
} else {
var current = this.head;
var index = 0;
var previous = null;
while (index < position) {
previous = current;
current = current.next;
index++;
}
//3. Let the previous next point to current next
previous.next = current.next;
current.next = null;
}
this.length -= 1;
return true;
}
/* remove(element); Removes an item from the list (by element) */
LinkedList.prototype.remove = function (element) {
var index = 0;
var current = this.head;
var previous = null;
while (current) {
if (current.data == element) {
if (index == 0) {
this.head = this.head.next;
} else {
previous.next = current.next;
}
this.length -= 1;
return true;
}
previous = current;
current = current.next;
index += 1;
}
return -1;
}
/* size(): length */
LinkedList.prototype.size = function () {
return this.length;
}
/* isEmpty(): length */
LinkedList.prototype.isEmpty = function () {
return this.length==0; }}var list = new LinkedList();
list.append('abc');
list.append('cbb');
list.append('axx');
console.log(list.tostring());
console.log(list.remove(' sss'));
console.log(list.tostring());
console.log(list.size());
console.log(list.isEmpty());
console.log(list);
</script>
</html>
Copy the code