JavaScript의 이중 연결 목록 및 이중 순환 연결 목록에 대한 자세한 설명
- 亚连원래의
- 2018-06-23 17:23:251371검색
이 글은 주로 JavaScript 데이터 구조 이중 연결 목록과 이중 순환 연결 목록의 구현을 소개합니다. 관심 있는 친구들이 참고할 수 있습니다.
이중 연결 목록과 일반 연결 목록의 차이점은 연결 목록에 있다는 것입니다. , 노드에는 다음 노드에 대한 링크만 있는 반면 이중 연결 목록에서는 링크가 양방향입니다. 즉, 한 링크는 다음 요소에 연결되고 다른 링크는 이전 요소에 연결됩니다.
이중 연결 목록은 목록을 반복하는 두 가지 방법(처음부터 끝까지 또는 그 반대로)을 제공합니다. 특정 노드의 다음 또는 이전 요소에 액세스할 수도 있습니다. 단방향 연결 목록에서는 목록을 반복하는 동안 찾고 있는 요소를 놓친 경우 목록의 시작점으로 돌아가서 반복을 다시 시작해야 합니다. 이것이 이중 연결 리스트의 장점입니다.
이중 연결 목록: 단방향 연결 목록은 한 방향으로만 연결 목록 노드를 순회할 수 있지만, 노드 포인터 필드에 정방향 포인터가 추가된 이중 연결 목록은 노드를 양방향으로 순회할 수 있습니다. 이를 통해 이중 연결 목록이 모든 노드에서 전체 연결 목록을 순회할 수 있습니다.
function DoublyLinkedList() {
var Node = function(element) {
this.element = element;
this.next = null;
this.prev = null;
};
var length = 0,
head = null,
tail = null;
this.append = function(element){
var node = Node(element),
current,
previous;
if(!head){
head = node;
tail = node;
}else{
current = head;
while(current){
previous = current;
current = current.next;
}
node.next = current;
current.prev = node;
previous.next = node;
node.prev = previous;
}
length++;
return true;
}
this.insert = function(position,element){
if(position > -1 && position < length){
var node = new Node(element),
current = head,
previous,
index = 0;
if(position === 0){
if(!head){
head = node;
tail = node;
}else{
node.next = current;
current.prev = node;
head = node;
}
}else if (position === length -1){
current = tail;
current.next = node;
node.prev = current;
}else {
while(index++ < position){
previous = current;
current = current.next;
}
node.next = current;
previous.next = node;
current.prev = node;
node.prev = previous;
}
length++;
return true;
}else{
return false;
}
};
this.removeAt = function(position){
if(position > -1 && position < length){
var current = head,
index = 0,
previous;
if (position === 0) {
head = current.next;
if(length === 1){
tail = null;
}else{
head.prev = null;
}
}else if(position === length - 1){
current = tail;
tail = current.prev;
tail.next = null;
} else{
while(index++ < position){
previous = current;
current = current.next;
}
previous.next = current.next;
current.next.prev = previous;
};
length-- ;
return current.element;
}else{
return false;
}
};
this.remove = function(element){
var current = head,
previous;
if(current.element === element){
head = current.next;
}
previous = current;
current = current.next;
while(current){
if (current.element = element) {
previous.next = current.next;
current.next.prev = previous;
}else{
previous = current;
current = current.next;
}
}
return false;
};
this.remove = function(){
if (length === 0) {
return false;
};
var current = head,
previous;
if(length === 1){
head = null;
tail = null;
length--;
return current.element;
}
while(current){
previous = current;
current = current.next;
}
previous.next = null;
length--;
return current.element;
};
this.indexOf = function(element){
var current = head,
index = 0;
while(current && index++ < length){
if (current.element === element) {
return 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;
};
this.getTail = function(){
return tail;
};
}양방향 순환 연결 리스트: 양방향 연결 리스트의 헤드 포인터와 테일 포인터를 연결하여 양방향 순환 연결 리스트를 형성합니다. 이런 연결리스트는 어떤 노드에서든 동시에 두 방향으로 노드를 순회할 수 있고, 노드를 쿼리하는 속도도 가장 빠르다.
/*双向循环链表*/
function DoublyCircularLinkedList(){
var Node = function(element){
this.element = element;
this.next = null;
this.prev = null;
};
var length = 0,
head = null,
tail = null;
this.append = function(element){
var node = new Node(element),
current,
previous;
if (!head) {
head = node;
tail = node;
head.prev = tail;
tail.next = head;
}else{
current = head;
while(current.next !== head){
previous = current;
current = current.next;
}
current.next = node;
node.next = head;
node.prev = current;
};
length++;
return true;
};
this.insert = function(position, element){
if(position >= 0 && position <= length){
var node = new Node(element),
index = 0,
current = head,
previous;
if(position === 0){
if(!head){
node.next = node;
node.tail = node;
head = node;
tail = node;
}else{
current.prev = node;
node.next = current;
head = node;
node.prev = tail;
}
}else if(position === length){
current = tail;
current.next = node;
node.prev = current;
tail = node;
node.next = head;
}else{
while(index++ < position){
previous = current;
current = current.next;
}
current.prev = node;
node.next = current;
previous.next = node;
node.prev = previous;
}
length++;
return true;
}else{
return false;
}
};
this.removeAt = function(position){
if(position > -1 && position < length){
var current = head,
index = 0,
previous;
if(position === 0){
current.next.previous = tail;
head = current.next;
}else if(position === length - 1){
current = tail;
current.prev.next = head;
head.prev = current.prev;
tail = current.prev;
}else{
while(index++ < position){
previous = current;
current = current.next;
}
previous.next = current.next;
current.next.prev = previous;
}
length--;
return true;
}else{
return false;
}
};
this.remove = function(element){
var current = head,
previous,
indexCheck = 0;
while(current && indexCheck < length){
if(current.element === element){
if(indexCheck === 0){
current.next.prev = tail;
head = current.next;
}else{
current.next.prev = previous;
previous.next = current.next;
}
length--;
return true;
}
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;
tail = null;
length--;
return current.element;
}
while(indexCheck++ < length){
previous = current;
current = current.next;
}
previous.next = head;
tail = previous.next;
length--;
return current.element;
};
this.indexOf = function(element){
var current = head,
index = 0;
while(current && index++ < length){
if(current.element === element){
return index;
}
current = current.next;
}
return false;
};
this.toString = function(){
var current = head,
indexCheck = 0,
string = '';
while(current && indexCheck < length){
string += current.element;
indexCheck++;
current = current.next;
}
return string;
};
this.isEmpty = function(){
return length === 0;
};
this.getHead = function(){
return head;
};
this.getTail = function(){
return tail;
};
this.size = function(){
return length;
};
}위 내용은 모두를 위해 제가 정리한 내용입니다. 앞으로 모든 사람에게 도움이 되기를 바랍니다.
관련 기사:
부모 노드가 선택되면 비활성화된 하위 노드도 선택되도록 Jstree에서 구현하는 방법
vue.js의 mint-ui에 캐러셀 차트를 통합하는 방법
In AngularJS 수집 데이터 순회 표시 구현 방법
위 내용은 JavaScript의 이중 연결 목록 및 이중 순환 연결 목록에 대한 자세한 설명의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!
성명：
본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.