1. The Basics of Linked Lists
7282 단어 DataStructuresDataStructures
1. What's special about linked lists?
- 순차적으로 연결된 value를 가진 data structure
- array보다 insertion/deletion이 효율적
- value의 메모리 주소들이 인접하지 않아도된다.
2. Linked lists vs arrays
노드를 접근할 경우
- array는 메모리에 인접한채로 있기 때문에, index를 통해 빠르게 접근 가능 -> O(1)
- Linked List는 메모리에 랜덤하게 저장되므로 특정 노드에 접근하려면, 첫 노드부터 순차적으로 접근해서 조회 가능 -> O(n)
새로운 노드를 삽입할 경우
- Array는 x를 삽입 시 메모리 주소를 한칸씩 밀어네고 O(n)의 복잡도 발생
- LinkedList는 삽입 할 노드의 next 메모리 주소만 변경
시간 복잡도
3. 코드 구현
class Node {
constructor(val) {
this.val = val;
this.next = null;
}
}
class LinkedList {
constructor() {
this.head = null;
}
append(val) {
if(this.head === null) {
this.head = new Node(val)
return;
}
let curr = this.head;
while(curr.next !== null) {
curr = curr.next;
}
curr.next = new Node(val)
}
print() {
let str = '';
let curr = this.head;
while (curr !== null) {
str += curr.val
curr = curr.next;
}
return str
}
contains(target) {
let curr = this.head;
while(curr !== null) {
if(curr.val === target) {
return true;
}
curr = curr.next
}
return false;
}
}
const list = new LinkedList();
참고 : Coderbyte - The Basics of Linked Lists
Author And Source
이 문제에 관하여(1. The Basics of Linked Lists), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@kimkevin90/The-Basics-of-Linked-Lists저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)