이중 연결 목록 구현

Big O 표기법을 이해하고 있다고 가정합니다. 예제는 JavaScript에 있습니다. 정보 참고자료 Gayle Laakmann McDowell의 "코딩 인터뷰 크래킹"

이중 연결 목록 이해

이중 연결 목록은 노드의 구조와 노드를 추가/제거하는 방식을 제외하면 단일 연결 목록과 매우 유사합니다.

노드 구조

이중 연결 리스트의 노드에는 이전 포인터, 다음 포인터, 값이 포함됩니다. prev 포인터는 이전 노드를 가리키고, next 포인터는 다음 노드를 가리킵니다. 본질적으로 이 목록은 각 노드에서 양방향으로 진행됩니다.

노드 추가

특정 인덱스에 새 노드(newNode)를 삽입하려면:

1. 현재 삽입 인덱스에 있는 노드를 임시 변수 nextNode에 저장합니다.

2. 이전 노드와 새 노드의 연결을 업데이트합니다.

   • 이전 노드의 다음 포인터를 newNode로 설정합니다.
   • newNode의 이전 포인터를 이전 노드로 설정합니다.

3. 새 노드를 다음 노드에 연결합니다.

   • newNode의 다음 포인터를 nextNode로 설정합니다.
   • nextNode의 이전 포인터를 newNode로 설정합니다.

노드 제거

특정 인덱스에서 노드를 제거하려면:

1. 이전 노드의 다음 포인터를 업데이트합니다.
   • 제거된 노드를 가리키도록 설정하세요.
2. 다음 노드의 이전 포인터를 업데이트합니다.
   • 제거되기 전의 노드를 가리키도록 설정하세요.

이렇게 하면 노드 제거로 인해 발생한 격차를 효과적으로 "연결"하고 목록의 무결성을 유지할 수 있습니다.

시간 복잡도 분석

• 이중 연결 리스트 내부 추가/제거 → $O(n)$O(n)

• 이중 연결 리스트의 머리 또는 꼬리에 추가/제거 → $O(1)$O(1)

자바스크립트 구현

클래식 OOP

class ListNode {
  constructor(value, prev = null, next = null) {
    this.value = value;
    this.prev = prev;
    this.next = next;
  }
}

class DoublyLinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this.size = 0;
  }

  // add a node to the head of the list
  addHead(value) {
    const newNode = new ListNode(value, null, this.head);
    if (this.head) {
      this.head.prev = newNode;
    } else {
      this.tail = newNode; // If list was empty, new node is also the tail
    }
    this.head = newNode;
    this.size++;
  }

  // Add a node to the tail of the list
  addTail(value) {
    const newNode = new ListNode(value, this.tail, null);
    if (this.tail) {
      this.tail.next = newNode;
    } else {
      this.head = newNode; // If list was empty, new node is also the head
    }
    this.tail = newNode;
    this.size++;
  }

  // Remove a node from the head of the list
  removeHead() {
    if (!this.head) return null; // List is empty
    const removedValue = this.head.value;
    this.head = this.head.next;
    if (this.head) {
      this.head.prev = null;
    } else {
      this.tail = null; // List became empty
    }
    this.size--;
    return removedValue;
  }

  // Remove a node from the tail of the list
  removeTail() {
    if (!this.tail) return null; // List is empty
    const removedValue = this.tail.value;
    this.tail = this.tail.prev;
    if (this.tail) {
      this.tail.next = null;
    } else {
      this.head = null; // List became empty
    }
    this.size--;
    return removedValue;
  }

  // Remove a node at a specific index
  removeAt(index) {
    if (index < 0 || index >= this.size) return null;
    let current;
    if (index < this.size / 2) {
      current = this.head;
      for (let i = 0; i < index; i++) {
        current = current.next;
      }
    } else {
      current = this.tail;
      for (let i = this.size - 1; i > index; i--) {
        current = current.prev;
      }
    }
    if (current.prev) current.prev.next = current.next;
    if (current.next) current.next.prev = current.prev;
    if (index === 0) this.head = current.next;
    if (index === this.size - 1) this.tail = current.prev;
    this.size--;
    return current.value;
  }

  // Get the size of the list
  getSize() {
    return this.size;
  }

  // Get the values in the list
  getValues() {
    const values = [];
    let current = this.head;
    while (current) {
      values.push(current.value);
      current = current.next;
    }
    return values;
  }
}

기능적 OOP

function ListNode(value, prev = null, next = null) {
  this.value = value;
  this.prev = prev;
  this.next = next;
}

function DoublyLinkedList() {
  this.head = null;
  this.tail = null;
  this.size = 0;
}

// Add a node to the head of the list
DoublyLinkedList.prototype.addHead = function(value) {
  const newNode = new ListNode(value, null, this.head);
  if (this.head) {
    this.head.prev = newNode;
  } else {
    this.tail = newNode;
  }
  this.head = newNode;
  this.size++;
};

// Add a node to the tail of the list
DoublyLinkedList.prototype.addTail = function(value) {
  const newNode = new ListNode(value, this.tail, null);
  if (this.tail) {
    this.tail.next = newNode;
  } else {
    this.head = newNode;
  }
  this.tail = newNode;
  this.size++;
};

// Remove a node from the head of the list
DoublyLinkedList.prototype.removeHead = function() {
  if (!this.head) return null;
  const removedValue = this.head.value;
  this.head = this.head.next;
  if (this.head) {
    this.head.prev = null;
  } else {
    this.tail = null;
  }
  this.size--;
  return removedValue;
};

// Remove a node from the tail of the list
DoublyLinkedList.prototype.removeTail = function() {
  if (!this.tail) return null;
  const removedValue = this.tail.value;
  this.tail = this.tail.prev;
  if (this.tail) {
    this.tail.next = null;
  } else {
    this.head = null;
  }
  this.size--;
  return removedValue;
};

// Remove a node at a specific index
DoublyLinkedList.prototype.removeAt = function(index) {
  if (index < 0 || index >= this.size) return null;
  let current;
  if (index < this.size / 2) {
    current = this.head;
    for (let i = 0; i < index; i++) {
      current = current.next;
    }
  } else {
    current = this.tail;
    for (let i = this.size - 1; i > index; i--) {
      current = current.prev;
    }
  }
  if (current.prev) current.prev.next = current.next;
  if (current.next) current.next.prev = current.prev;
  if (index === 0) this.head = current.next;
  if (index === this.size - 1) this.tail = current.prev;
  this.size--;
  return current.value;
};

// Get the size of the list
DoublyLinkedList.prototype.getSize = function() {
  return this.size;
};

// Get the values in the list
DoublyLinkedList.prototype.getValues = function() {
  const values = [];
  let current = this.head;
  while (current) {
    values.push(current.value);
    current = current.next;
  }
  return values;
};

위 내용은 이중 연결 목록 구현의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!