JavaScript 데이터 구조 및 알고리즘 연결리스트

연결리스트 소개

연결된 목록은 일반적인 데이터 구조이자 선형 목록이기도 하지만 데이터를 선형 순서로 저장하지 않습니다. 대신 각 노드에는 다음 노드에 대한 포인터가 저장됩니다. 그림을 보시면 이해가 되실 겁니다. (C언어를 공부하신 분들은 이해가 더 쉬울 수도 있습니다.)
연결된 목록 구조를 사용하면 데이터 크기를 미리 알아야 하는 배열의 단점(C 언어의 배열에는 미리 정의된 길이가 필요함)을 극복할 수 있습니다. 연결된 목록 구조는 컴퓨터 메모리 공간을 최대한 활용하고 달성할 수 있습니다. 유연한 동적 메모리 관리.
다음으로, 두 가지 일반적인 연결 목록, 즉 단방향 연결 목록과 JavaScript의 이중 연결 목록 구현을 소개합니다.

단방향 연결 리스트

연결된 목록의 가장 간단한 형태는 단방향 연결 목록입니다. 연결 목록의 노드는 두 부분으로 구성됩니다. 첫 번째 부분은 자체 정보를 저장하고 두 번째 부분은 다음 노드에 대한 포인터를 저장합니다. 마지막 노드는 NULL을 가리킵니다:

JavaScipt에서 단방향 연결 리스트 구현

먼저 생성자를 만듭니다.

/**
 * 单向链表构造函数
 */
function LinkedList() {
 /**
  * 单向链表中节点的构造函数
  * @param {Any} element 要传入链表的节点
  */
 var Node = function(element) {
  this.element = element;
  //下个节点的地址
  this.next = null;
 }

 //单向链表的长度
 var length = 0;
 //单向链表的头结点，初始化为NULL
 var head = null;
}

로그인 후 복사

단방향 연결 리스트 생성자가 스택과 큐보다 훨씬 더 복잡하다는 것을 쉽게 알 수 있습니다.
단방향 연결 목록에는 다음 메서드가 필요합니다.

append(element): 연결리스트 끝에 요소를 추가합니다
insert(position,element): 단방향 연결 리스트의 특정 위치에 요소를 삽입합니다
indexOf(element): 단방향 연결 리스트에서 요소의 위치 찾기
remove(element): 주어진 요소를 제거합니다
removeAt(position): 단방향 연결 리스트의 특정 위치에 있는 요소를 제거합니다
getHead(): 단방향 연결 리스트의 헤드를 가져옵니다
isAmpty(): 단방향 연결 목록이 비어 있는지 확인하고, 비어 있으면 true를 반환합니다.
toString(): 연결리스트의 모든 내용을 문자열로 출력합니다
size(): 단방향 연결 리스트의 길이를 반환합니다

추가 방법:

설명: 단방향 연결 목록의 끝에 요소를 추가합니다.
구현:

/**
 * 向单向链表尾部添加元素
 * @param {Any} element 要加入链表的节点
 */
this.append = function(element) {
 var node = new Node(element);
 var current;

 if (head == null) {
  head = node;
 } else {
  // 当前项等于链表头部元素.
  // while循环到最后一个，从而将该节点加入链表尾部。
  current = head;
  // 当next为null时，判定为false。退出循环。
  while (current.next) {
   current = current.next;
  }
  current.next = node;
 }
 length++;
};

로그인 후 복사

삽입 방법:

설명: 단방향 연결 목록의 특정 위치에 요소를 삽입합니다.
구현:

/**
 * 向单向链表中插入某个元素
 * @param {Number} position 要插入的位置
 * @param {Any} element 要插入的元素
 * @return {Boolean}     插入成功返回true，失败返回false
 */
this.insert = function(position, element) {
 if (position >= 0 && position <= length) {
  var node = new Node(element);
  var current = head;
  var previous;
  var index = 0;

  if (position == 0) {
   node.next = current;
   head = node;
  } else {
   while (index++ < position) {
    previous = current;
    current = current.next;
   }

   previous.next = node;
   node.next = current;
  }

  length++;
  return true;
 } else {
  return false;
 }
};

로그인 후 복사

indexOf 메소드:

설명: 단방향 연결 목록에서 요소의 위치를 찾습니다.
구현:

/**
 * 寻找某个元素在单向链表中的位置
 * @param {Any} element 要寻找的元素
 * @return {Number}     返回值>=0则代表找到相应位置
 */
this.indexOf = function(element) {
 var current = head;
 var index = -1;

 while (current) {
  if (element === current.element) {
   return index;
  }
  index++;
  current = current.next;
 }

 return -1;
};

로그인 후 복사

제거 방법:

설명: 해당 요소를 제거합니다.
구현:

/**
 * 移除给定的元素
 * @param {Any} element 要移除的元素
 * @return {Number}     返回值>=0表示移除成功
 */
this.remove = function(element) {
 var index = this.indexOf(element);
 return this.removeAt(index);
};

로그인 후 복사

removeAt 메소드:

설명: 단방향 연결 목록의 특정 위치에 있는 요소를 제거합니다.
구현:

/**
 * 移除单向链表中某一个元素
 * @param {Number} position 要移除元素的位置
 * @return {Any}     移除成功返回被移除的元素，不成功则返回NULL
 */
this.removeAt = function(position) {
 if (position > -1 && position < length) {
  var current = head;
  var previous;
  var index = 0;

  if (position == 0) {
   // 因为之前head指向第一个元素，现在把head修改为指向第二个元素。
   // 核心概念在于链表前后全靠指针链接，而非数组一般。
   // 所以只需要改变head的元素。
   head = current.next;
  } else {
   while (index++ < position) {
    // previous指要操作元素位置之前的那个元素，current表示之后的那个元素。
    previous = current;
    current = current.next;
   }

   previous.next = current.next;
  }

  length--;

  return current.element;
 } else {
  return null;
 }
};

로그인 후 복사

getHead 메소드:

설명: 단방향 연결 목록의 헤드를 가져옵니다.
구현:

/**
 * 获取单向链表的头部
 * @return {Any} 单向链表的头部
 */
this.getHead = function() {
 return head;
}

로그인 후 복사

isAmpty, toString, 크기 방법

구현:

/**
 * 判断单向链表是否为空
 * @return {Boolean} 为空则返回true，不为空则返回false
 */
this.isAmpty = function() {
 return length === 0
};

/**
 * 将链表所有内容以字符串输出
 * @return {String} 要输出的字符串
 */
this.toString = function() {
 var current = head;
 var string = '';

 while (current) {
  string += current.element;
  current = current.next;
 }
 return string;
};

/**
 * 返回单向链表长度
 * @return {Number} 单向链表的长度
 */
this.size = function() {
 return length;
};

로그인 후 복사

이중 연결 리스트

이중 연결 목록은 단방향 연결 목록과 매우 유사합니다. 단방향 연결 리스트에는 다음 노드에 대한 링크만 있습니다. 그러나 이중 연결 리스트에는 이전 노드에 대한 양방향 링크가 있습니다.

JavaScipt에서 이중 연결 목록 구현

첫째, 여전히 생성자입니다.

/**
 * 双向链表的构造函数
 */
function DoublyLinkedList() {
 /**
  * 双向链表中节点的构造函数
  * @param {Any} element 要传入链表的元素
  */
 var Node = function(element) {
  this.element = element;
  this.prev = null;
  this.next = null;
 }

 //双向链表的长度
 var length = 0;
 //双向链表的头结点，初始化为NULL
 var head = null;
 //双向链表的尾结点，初始化为NULL
 var tail = null;
}

로그인 후 복사

이중 연결 목록에는 다음 방법이 필요합니다.

append(element): 이중 연결 리스트 끝에 요소를 추가합니다
insert(position,element): 이중 연결 리스트의 특정 위치에 요소를 삽입합니다
removeAt(position): 이중 연결 리스트의 특정 위치에 있는 요소를 제거합니다
showHead(): 이중 연결 리스트의 헤드를 가져옵니다
showLength(): 이중 연결 리스트의 길이를 가져옵니다
showTail(): 이중 연결 리스트의 꼬리 가져오기

추가 방법:

설명: 이중 연결 리스트 끝에 요소를 추가합니다
구현:

/**
 * 向链表尾部添加元素
 * @param {Any} element 要加入链表的节点
 * @return {Any}     加入链表的节点
 */
this.append = function(element) {
 var node = new Node(element);

 if (head === null) {
  head = node;
  tail = node;
 } else {
  var previous;
  var current = head;

  while (current.next) {
   current = current.next;
  }

  current.next = node;
  node.prev = current;
  tail = node;
 }

 length++;
 return node;
};

로그인 후 복사

삽입 방법:

설명: 이중 연결 리스트의 특정 위치에 요소를 삽입합니다.
구현:

/**
 * 向链表中插入某个元素
 * @param {Number} position 要插入的位置
 * @return {Boolean}     插入成功返回true，失败返回false
 */
this.insert = function(position, element) {
 if (position >= 0 && position <= length) {

  var node = new Node(element);
  var index = 0;
  var previous;
  var current = head;

  if (position === 0) {

   if (head === null) {
    head = node;
    tail = node;
   } else {
    current.prev = node;
    node.next = current;
    head = node;
   }
  } else if (position === length) {

   current = tail;
   current.next = node;
   node.prev = current;
   tail = node;
  } else {

   while (index++ < position) {
    previous = current;
    current = current.next;
   }

   previous.next = node;
   node.prev = previous;
   current.prev = node;
   node.next = current;
  }

  length++;
  return true;
 } else {
  return false;
 }
};

로그인 후 복사

removeAt 메소드:

설명: 이중 연결 리스트의 특정 위치에 있는 요소를 제거합니다.
구현:

/**
 * 移除链表中某一个元素
 * @param {Number} position 要移除元素的位置
 * @return {Any}       移除成功返回被移除的元素，不成功则返回false
 */
this.removeAt = function(position) {
 if (position > -1 && position < length) {
  var current = head;
  var index = 0;
  var previous;

  if (position === 0) {
   head = current.next;

   if (length === 1) {
    tail = null;
    head.prev = null;
   }
  } else if (position === length - 1) {
   current = tail;
   tail = current.prev;
   tail.next = null;
  } else {
   while (index++ < position) {
    previous = current.prev;
    current = current.next;
   }
   previous.next = current.next;
   current.next.prev = previous;
  }

  length--;
  return current.element;
 } else {
  return false;
 }
};

로그인 후 복사

showHead, showLength, showTail 메소드

구현:

/**
 * 获取链表的头部
 * @return {Any} 链表的头部
 */
this.showHead = function() {
 return head;
};

/**
 * 获取链表长度
 * @return {Number} 链表长度
 */
this.showLength = function() {
 return length;
};

/**
 * 获取链表尾部
 * @return {Any} 链表尾部
 */
this.showTail = function() {
 return tail;
};

로그인 후 복사

인상수

연결된 목록에 대한 이 섹션에서는 기본적으로 모든 코드를 요구 사항에 따라 먼저 작성한 다음 작성한 후 책과 비교합니다. 그는 순식간에 쓰레기로 변한 것으로 밝혀졌습니다. 내 글에는 숨겨진 구덩이가 많고, 논리도 매우 혼란스럽다. 아직 너무 어린 것 같습니다.