JavaScript에서 단일 연결 목록과 순환 연결 목록을 사용하는 방법
- 亚连원래의
- 2018-06-23 17:27:231619검색
이 글에서는 자바스크립트의 단일 연결 목록과 순환 연결 목록의 데이터 구조를 주로 소개하고, 자바스크립트가 단일 연결 목록과 순환 연결 목록을 어떻게 구현하는지 자세히 소개합니다. 관심 있는 분들은 자세히 알아보세요
데이터 구조 서문 시리즈:
프로그래머의 기본 지식으로서의 데이터 구조는 우리 각자가 확실하게 파악해야 합니다. 최근에는 당시 파놓은 구덩이를 보완하기 위해 데이터 구조에 대한 두 번째 연구도 시작했습니다. . . . . . 수업을 들을 때는 강의만 따라했고, 데이터 구조를 직접 구현해 본 적은 없었고, 데이터 구조를 사용하여 문제를 해결하는 것은커녕요. 이제 구멍을 메우고 투쟁할 때입니다. 제 블로그를 읽는 아이들에게 아직 학교에 다니고 있다면 지금 파고든 구멍을 메워야 한다는 점을 상기시키고 싶습니다. 두 배의 노력으로 사람의 능력 등에 직접적인 영향을 미칠 것입니다. . . . . . 스스로 구멍을 파지 마세요
본점으로 들어가겠습니다. 연결 목록의 데이터 구조 지식에 대해 간략하게 소개합니다.
연결 목록은 물리적 저장소의 비선형 및 비연속 데이터 구조입니다. 단위(논리적으로 선형임), 각 노드는 데이터 필드와 포인터 필드라는 두 개의 필드로 구성됩니다. 데이터 필드에는 실제 데이터가 저장되고, 포인터 필드에는 연결리스트의 다음 요소나 이전 요소를 가리키는 포인터 정보가 저장된다. 연결된 목록의 저장이 물리적 단위에서 불연속적인 것은 바로 포인터의 존재 때문입니다.
연결된 목록의 장점과 단점은 똑같이 명백합니다. 선형 목록에 비해 연결 목록은 요소 이동이 필요한 선형 목록(배열)과 달리 포인터 정보만 수정하면 작업을 완료할 수 있기 때문에 노드를 추가하고 삭제하는 데 더 효율적입니다. 마찬가지로 연결된 목록의 길이는 이론적으로 무한하며(메모리 용량 내에서) 길이는 동적으로 변경될 수 있으므로 선형 목록에 비해 큰 이점이 있습니다. 이에 따라 선형 테이블은 노드에 무작위로 액세스할 수 없고 연결된 목록을 따라 포인터 순회 쿼리를 통해서만 액세스할 수 있으므로 데이터 요소에 액세스하는 효율성이 상대적으로 낮습니다.
다음은 JS 파트
에 캡슐화된 일반적인 메서드와 설명입니다.
| Method | Description |
|---|---|
| append(element) | 연결 목록 끝에 노드 요소 추가 |
| insert( position,element) | 위치 position에 노드 요소 삽입 |
| removeAt(position) | 인덱스 값 position에 따라 노드 삭제 |
| remove(element) | 해당 노드 검색 및 삭제 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 = '';
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 = '',
indexCheck = 0;
while(current && indexCheck < length){
string += current.element;
current = current.next;
indexCheck++;
}
return string;
};
}사용법:
수업 외 확장 방법:
위 내용은 제가 모든 사람을 위해 정리한 내용입니다. 앞으로 모든 사람에게 도움이 되기를 바랍니다.
관련 기사:
Vue.js의 구성 요소 간 순환 참조를 구현하는 방법
nodejs에서 초과된 최대 호출 스택 오류를 해결하는 방법
에서 블로그 관리 플랫폼을 구현하는 방법위 내용은 JavaScript에서 단일 연결 목록과 순환 연결 목록을 사용하는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!