Recently, I was reading the book "Javascript Data Structure and Algorithm" to supplement my knowledge of data structure and algorithm. I felt that I was lacking in this area.
Linked list: Stores an ordered collection of elements, but unlike an array, the elements in a linked list are not placed continuously in memory. Each element consists of a node that stores the element itself and a reference (also called a pointer or link) to the next element.
Benefits: You can add or remove any item, it will expand as needed without moving other elements. The difference between
and array:
Array: You can directly access any element at any position;
Linked list: If you want to access an element in the linked list, you need to iterate the list from the starting point (header) until you find what you want Elements.
Take some notes.
function LinkedList(){ var Node = function(element){ this.element = element this.next = null } var length = 0 var head = null this.append = function(element){ var node = new Node(element) var current if(head == null){ //链表为空 head = node }else{ //链表不为空 current = head //循环链表,直到最后一项 while(current.next){ current = current.next } current.next = node } length ++ //更新链表长度 } this.insert = function(position,element){ var node = new Node(element) var current = head var previous var index = 0 if(position>=1 && position<=length){ //判断是否越界 if(position === 0){ //插入首部 node.next = current head = node }else{ while(index++ < position){ previous = current current = current.next } node.next = current previous.next = node } length ++ //更新链表长度 return true }else{ return false } } this.indexOf = function(element){ var current = head var index = -1 while(current){ if (element === current.element) { return index } index++ current = current.next } return -1 } this.removeAt = function(position){ if(position>-1 && position<length){ //判断是否越界 var current = head var previous var 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 } } this.remove = function(element){ var index = this.indexOf(element) return this.removeAt(index) } this.isEmpty = function(){ return length == 0 } this.size = function(){ return length } this.toString = function(){ var current = head var string = "" while(current){ string = "," + current.element current = current.next } return string.slice(1) } this.getHead = function(){ return head } }