JavaScript 데이터 구조 단일 연결 목록 및 순환 연결 목록 예제 공유

이 글은 주로 단일 연결 목록과 순환 연결 목록의 JavaScript 데이터 구조를 소개하며, JavaScript가 단일 연결 목록과 순환 연결 목록을 구현하는 방법도 자세히 소개합니다. 관심 있는 분들에게 도움이 되길 바랍니다.

본점에 도달하면 다음은 연결 목록의 데이터 구조 지식에 대한 간략한 소개입니다.

연결 목록은 물리적 저장 단위의 비선형 및 불연속 데이터 구조이며(데이터 논리에서는 선형입니다) A 노드는 데이터 필드와 포인터 필드라는 두 개의 필드로 구성됩니다. 데이터 필드에는 실제 데이터가 저장되고, 포인터 필드에는 연결리스트의 다음 요소나 이전 요소를 가리키는 포인터 정보가 저장된다. 연결된 목록의 저장이 물리적 단위에서 불연속적인 것은 바로 포인터의 존재 때문입니다.

연결된 목록의 장점과 단점은 똑같이 명백합니다. 선형 목록에 비해 연결 목록은 요소 이동이 필요한 선형 목록(배열)과 달리 포인터 정보만 수정하면 작업을 완료할 수 있기 때문에 노드를 추가하고 삭제하는 데 더 효율적입니다. 마찬가지로 연결된 목록의 길이는 이론적으로 메모리 용량 내에서 무한하며 길이는 동적으로 변경될 수 있으므로 선형 목록에 비해 큰 이점이 있습니다. 이에 따라 선형 테이블은 노드에 무작위로 액세스할 수 없고 연결된 목록을 따라 포인터 순회 쿼리를 통해서만 액세스할 수 있으므로 데이터 요소에 액세스하는 효율성이 상대적으로 낮습니다.

다음은 JS 파트

에 캡슐화된 일반적인 메서드와 설명입니다.

Method	Description
append(element)	연결 목록 끝에 노드 요소 추가
insert(위치, 요소)	위치에 노드 요소 삽입
removeAt(position)	인덱스 값 위치에 따라 노드 삭제
remove(element)	해당 노드 요소 검색 및 삭제
remove()	링크드 리스트의 마지막 노드 삭제
indexOf(element)	주어진 노드 요소의 인덱스 값을 찾아 반환
isEmpty()	연결 목록이 비어 있습니다
size()	연결 목록의 길이를 가져옵니다
toString()	문자열 출력으로 변환
getHead()	헤드 노드 가져오기
getTail ()	Get The tail node

일반적으로 사용되는 다양한 방법에 대한 알고리즘 설명은 여기에서는 누구나 쉽게 읽고 이해할 수 있다고 믿습니다.

단일 연결 리스트:

function LinkedList(){ 
 /*节点定义*/ 
 var Node = function(element){ 
  this.element = element; //存放节点内容 
  this.next = null; //指针 
 } 
 
 var length = 0, //存放链表长度 
  head = null; //头指针 
 
 this.append = function(element){ 
  var node = new Node(element), 
   current; //操作所用指针 
 
  if (!head){ 
   head = node; 
  }else { 
   current = head; 
 
   while(current.next){ 
    current = current.next; 
   } 
 
   current.next = node; 
  } 
 
  length++; 
  return true; 
 }; 
 
 this.insert = function(position, element){ 
  if (position >= 0 && position <= length) { 
   var node = new Node(element), 
    current = head, 
    previous, 
    index = 0; 
 
   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.removeAt = function(position){ 
  if(position > -1 && position < length){ 
   var current = head, 
    previous, 
    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 current = head, 
   previous; 
 
  if(element === current.element){ 
   head = current.next; 
   length--; 
   return true; 
  } 
  previous = current; 
  current = current.next; 
 
  while(current){ 
   if(element === current.element){ 
    previous.next = current.next; 
    length--; 
    return true; 
   }else{ 
    previous = current; 
    current = current.next; 
   } 
  } 
  return false; 
 }; 
 
 this.remove = function(){ 
  if(length < 1){ 
   return false; 
  } 
 
  var current = head, 
  previous; 
 
  if(length == 1){ 
   head = null; 
   length--; 
   return current.element; 
  } 
 
  
  while(current.next !== null){ 
   previous = current; 
   current = current.next; 
  } 
 
  previous.next = null; 
  length--; 
  return current.element; 
 }; 
 
 this.indexOf = function(element){ 
  var current = head, 
   index = 0; 
 
  while(current){ 
   if(element === current.element){ 
    return index; 
   } 
   index++; 
   current = current.next; 
  } 
 
  return false; 
 }; 
 
 this.isEmpty = function(){ 
  return length === 0; 
 }; 
 
 this.size = function(){ 
  return length; 
 }; 
 
 this.toString = function(){ 
  var current = head, 
   string = &#39;&#39;; 
 
  while(current){ 
   string += current.element; 
   current = current.next; 
  } 
  return string; 
 };  
 
 this.getHead = function(){ 
  return head; 
 } 
  
}

순환 연결 리스트: 단일 연결 리스트를 기반으로 테일 노드의 포인터를 헤드 노드로 향하게 하여 순환 연결 리스트를 형성합니다. 순환 연결 리스트의 모든 노드에서 시작하여 전체 연결 리스트를 탐색할 수 있습니다.

function CircularLinkedList(){ 
 var Node = function(element){ 
  this.element = element; 
  this.next = null; 
 } 
 
 var length = 0, 
  head = null; 
 
 this.append = function(element){ 
  var node = new Node(element), 
   current; 
 
  if (!head) { 
   head = node; 
   node.next = head; 
  }else{ 
   current = head; 
 
   while(current.next !== head){ 
    current = current.next; 
   } 
 
   current.next = node; 
   node.next = head; 
  }; 
 
  length++; 
  return true; 
 }; 
 
 this.insert = function(position, element){ 
  if(position > -1 && position < length){ 
   var node = new Node(element), 
    index = 0, 
    current = head, 
    previous; 
 
 
   if (position === 0) { 
 
    node.next = head; 
    head = node; 
 
   }else{ 
 
    while(index++ < position){ 
     previous = current; 
     current = current.next; 
    } 
 
    previous.next = node; 
    node.next = current; 
 
   }; 
 
   length++; 
   return true; 
  }else{ 
   return false; 
  } 
 }; 
 
 this.removeAt = function(position){ 
  if(position > -1 && position < length){ 
   var current = head, 
    previous, 
    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 current = head, 
   previous, 
   indexCheck = 0; 
 
  while(current && indexCheck < length){ 
   if(current.element === element){ 
    if(indexCheck == 0){ 
     head = current.next; 
     length--; 
     return true; 
    }else{ 
     previous.next = current.next; 
     length--; 
     return true; 
    } 
   }else{ 
    previous = current; 
    current = current.next; 
    indexCheck++; 
   } 
  } 
  return false; 
 }; 
 
 this.remove = function(){ 
  if(length === 0){ 
   return false; 
  } 
 
  var current = head, 
   previous, 
   indexCheck = 0; 
 
  if(length === 1){ 
   head = null; 
   length--; 
   return current.element; 
  } 
 
  while(indexCheck++ < length){ 
   previous = current; 
   current = current.next; 
  } 
  previous.next = head; 
  length--; 
  return current.element; 
 }; 
 
 this.indexOf = function(element){ 
  var current = head, 
   index = 0; 
 
  while(current && index < length){ 
   if(current.element === element){ 
    return index; 
   }else{ 
    index++; 
    current = current.next; 
   } 
  } 
  return false; 
 }; 
 
 
 this.isEmpty = function(){ 
  return length === 0; 
 }; 
 
 this.size = function(){ 
  return length; 
 }; 
 
 this.toString = function(){ 
  var current = head, 
   string = &#39;&#39;, 
   indexCheck = 0; 
 
  while(current && indexCheck < length){ 
   string += current.element; 
   current = current.next; 
   indexCheck++; 
  } 
 
  return string; 
 };  
 
}

사용법:

클래스 외부의 확장 방법:

관련 권장 사항:

JavaScript 데이터 구조에서 이중 연결 목록의 사용 정의 예

자바스크립트 데이터 구조의 우선순위 큐와 순환 큐

자바스크립트 데이터 구조의 이진 탐색 트리 정의 및 표현 방법에 대한 자세한 설명

위 내용은 JavaScript 데이터 구조 단일 연결 목록 및 순환 연결 목록 예제 공유의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!