JavaScript 데이터 구조 연결리스트 지식에 대한 자세한 설명

최근 데이터 구조와 알고리즘에 대한 지식을 보충하기 위해 "자바스크립트 데이터 구조와 알고리즘"이라는 책을 읽다가 이 분야에 부족함을 느꼈습니다.

연결된 목록: 요소의 순서가 지정된 컬렉션을 저장하지만 배열과 달리 연결 목록의 요소는 메모리에 연속적으로 배치되지 않습니다. 각 요소는 요소 자체를 저장하는 노드와 다음 요소에 대한 참조(포인터 또는 링크라고도 함)로 구성됩니다.

이점: 모든 항목을 추가하거나 제거할 수 있으며 다른 요소를 이동하지 않고도 필요에 따라 확장됩니다.

과 배열의 차이점:

배열: 모든 위치의 모든 요소에 직접 액세스할 수 있습니다.

연결 목록: 원하는 연결된 목록에 액세스하려면 필요한 요소를 찾을 때까지 목록의 요소를 시작점(헤더)부터 반복해야 합니다.

몇 가지 메모를 하세요.

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