DSA LinkedList
1.0.0
노드 클래스를 나열합니다
class ListNode {
constructor(data) {
this.data = data
this.next = null
}
}
링크 된 목록 클래스
class LinkedList {
constructor(head = null) {
this.head = head
}
}
링크 된 목록을 만듭니다
let node1 = new ListNode(2)
let node2 = new ListNode(5)
node1.next = node2
let list = new LinkedList(node1)
console.log(list.head.next.data) //returns 5
size() {
let count = 0;
let node = this.head;
while (node) {
count++;
node = node.next
}
return count;
}
const ListFunctions = {
display: (linkedList) => {
items = [];
if (linkedList.head === null) {
return "The list is empty";
} else {
let currNode = linkedList.head;
while (currNode.next !== null) {
items.push(currNode.data);
currNode = currNode.next;
}
items.push(currNode.data);
}
return `Linked List Items: ${items.join("->")}`;
}
isEmpty: (linkedList) => {
if (linkedList.head === null) {
return `This list is empty`;
}
return `There are items in this list`;
}
find(item) {
let currNode = this.head;
if (!this.head) {
return null;
}
while (currNode.data !== item) {
if (currNode.next === null) {
return null;
} else {
currNode = currNode.next;
}
}
return currNode;
}
}
clear() {
this.head = null;
}
remove(item) {
if (!this.head) {
return null;
}
if (this.head.data === item) {
this.head = this.head.next;
return;
}
let currNode = this.head;
let previousNode = this.head;
while (currNode !== null && currNode.data !== item) {
previousNode = currNode;
currNode = currNode.next;
}
if (currNode === null) {
return;
}
previousNode.next = currNode.next;
}
insertFirst(item) {
this.head = new _Node(item, this.head);
}
insertLast(item) {
if (this.head === null) {
this.insertFirst(item);
} else {
let tempNode = this.head;
while (tempNode.next !== null) {
tempNode = tempNode.next;
}
tempNode.next = new _Node(item, null);
}
}
insertBefore(item, key) {
if (!this.head) {
return;
}
if (this.head.data === key) {
this.insertFirst(item);
return;
}
let currNode = this.head;
let previousNode = this.head;
while (currNode !== null && currNode.data !== key) {
previousNode = currNode;
currNode = currNode.next;
}
if (currNode === null) {
console.log(`key value not found`);
return;
}
previousNode.next = new _Node(item, currNode);
}
insertAfter(item, key) {
if (!this.head) {
return;
}
if (this.head.data === key) {
this.insertFirst(item);
return;
}
let currNode = this.head;
let nextNode = this.head;
while (currNode !== null && currNode.data !== key) {
currNode = nextNode;
nextNode = nextNode.next;
}
if (currNode === null) {
console.log(`key value not found`);
return;
}
currNode.next = new _Node(item, nextNode);
}
getLast() {
let lastNode = this.head;
if (lastNode) {
while (lastNode.next) {
lastNode = lastNode.next
}
}
return lastNode
}
getFirst() {
return this.head;
}
findPrevious: (linkedList, key) => {
if (linkedList.head === null) {
return null;
}
let prevNode;
let currNode = linkedList.head;
while (currNode.data !== key) {
prevNode = currNode;
currNode = currNode.next;
}
return `The previous node is ${prevNode.data}`;
}
이 드릴에서는 링크 된 목록을 작성하고 핵심을 구현하고 일부 보충 작업을 연습합니다. 또한 링크 된 목록을 사용하여 인터뷰 질문을 해결합니다. 이러한 각 운동에 대해 큰 O를 평가하는 것을 잊지 마십시오. 하나 이상의 샘플 입력 및 출력을 명시하여 각 문제를 시작하십시오.
링크 된 목록 클래스와 이러한 핵심 함수 (InsertFirst, InsertLast, Remove, Find)를 처음부터 작성하십시오.
링크 된 목록 클래스에서 작동하는 다음 기능을 구현하십시오. 이들은 링크 된 목록 클래스의 메소드 대신 자유 함수 여야하므로 링크 된 목록 클래스 외부에서 구현하십시오. 연습 1에서 생성 된 목록을 사용하여 각 기능을 테스트하십시오.
IDE에서 실행하지 않고 다음 함수를 분석하여 해결하려는 문제를 결정하십시오. 이 알고리즘의 시간 복잡성은 얼마입니까?
function WhatDoesThisProgramDo(lst) {
let current = lst.head;
while (current !== null) {
let newNode = current;
while (newNode.next !== null) {
if (newNode.next.value === current.value) {
newNode.next = newNode.next.next;
}
else {
newNode = newNode.next;
}
}
current = current.next;
}
}
링크 된 목록을 되돌리기 위해 알고리즘을 작성하십시오. 알고리즘의 시간 복잡성은 선형이어야합니다 (O (n)). 이 연습의 경우 링크 된 목록을 리버스로 인쇄하거나 다른 링크 된 목록을 사용하여 값을 역 순서로 저장하도록 요청하지 않습니다. 귀하의 프로그램은 주어진 단일 링크 된 목록의 방향을 뒤집어 야합니다. 다시 말해, 모든 포인터는 뒤로 향해야합니다. 보너스 : 재귀 및 반복 알고리즘을 사용 하여이 문제를 해결하십시오.
링크 된 목록의 끝에서 세 번째 요소를 찾으려면 알고리즘을 작성하십시오. 참고 링크 된 목록 클래스에 길이 속성을 추가하려는 유혹이있을 수 있습니다. 길이 속성은 링크 된 목록의 일반적인 속성이 아니므로 귀하에게 제공되는 링크 된 목록 클래스를 수정하지 마십시오.
링크 된 목록의 중간 요소를 찾으려면 알고리즘을 작성하십시오. 참고 링크 된 목록 클래스에 길이 속성을 추가하려는 유혹이있을 수 있습니다. 길이 속성은 링크 된 목록의 일반적인 속성이 아니므로 귀하에게 제공되는 링크 된 목록 클래스를 수정하지 마십시오. 또한 size () 함수를 사용하여 링크 된 목록의 크기를 찾아 반으로 나누면 링크 된 목록의 올바른 중간을 찾을 수 없습니다. 따라서 이러한 접근 방식 중 하나를 사용하지 마십시오.
링크 된 목록에 사이클이 있는지 여부를 찾기 위해 알고리즘을 작성하십시오 (예 : 목록의 노드가 목록의 이전 노드를 가리키는 다음 값이 있는지 여부). 이 연습의 경우 Cyclelist라는 이름으로 링크 된 목록을 작성하십시오. 목록에 노드를 삽입하여 사이클이 있도록하십시오. 그런 다음 사이클리스트 기능으로 프로그램을 테스트하십시오.
이중 링크 된 목록을 구현하십시오. 이중 링크 된 목록의 주요 기능은 삽입 (첫 번째, 마지막, 전, 후 및 AT), 제거 및 찾기입니다. 기능 maindll을 작성하고 그 안에 이중 링크 된 목록 DLL을 만들고 Aquaria, Caprica, Gemenon, Picon, Sagittaron 등 다음 항목을 추가하십시오.
위의 이중 링크 목록이 주어지면 이중 링크 된 목록을 뒤집는 프로그램을 작성하십시오. 이 구현은 단일 링크 된 목록을 되돌리는 것과 어떻게 다릅니 까?
