최근 데이터 구조와 알고리즘에 대한 지식을 보충하기 위해 "자바스크립트 데이터 구조와 알고리즘"이라는 책을 읽다가 이 분야에 부족함을 느꼈습니다.
연결된 목록: 요소의 순서가 지정된 컬렉션을 저장하지만 배열과 달리 연결 목록의 요소는 메모리에 연속적으로 배치되지 않습니다. 각 요소는 요소 자체를 저장하는 노드와 다음 요소에 대한 참조(포인터 또는 링크라고도 함)로 구성됩니다.
이점: 모든 항목을 추가하거나 제거할 수 있으며 다른 요소를 이동하지 않고도 필요에 따라 확장됩니다.
과 배열의 차이점:
배열: 모든 위치의 모든 요소에 직접 액세스할 수 있습니다.
연결 목록: 원하는 연결된 목록에 액세스하려면 필요한 요소를 찾을 때까지 목록의 요소를 시작점(헤더)부터 반복해야 합니다.
몇 가지 메모를 하세요.
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 } }