Linked List?
head,tail,length를 가지는 자료구조- node로 구성되어 있으며 각 node는 value를 가진다.
- node는 다른 노드로 연결되는
pointer를 가진다. next포인터만 가지는 Singly Linked List와,next,prev포인터를 가지는 doubly Linked List가 있다.
Linked List를 사용하는 이유
- Linked List는 배열과 비교해
insertion과desertion에 좋은 효율을 가진다. - 따라서, 빈번하게 삽입과 삭제를 해야하는 경우 Linkes List를 사용하는게 좋다.
Lists VS Arrays
List
- List는 index가 없다.
- random access가 불가능하다.
- 다른 node들과
next,prev포인터를 이용해 연결된다.
Arrays
- index가 있다.
- 특정한 index에 접근할 필요가 있을때 효율적이다.
shiftunshift같이 맨 앞의 요소를 추가, 삭제, 변경 할때 효율이 좋지 않다.- 뒤에 있는 모든 요소를 다음으로 넘겨야 하므로 O(N)의 시간복잡도를 가지기 때문이다.
Linked List 구현
Singly Linked List class Node{
constructor(val) {
this.val = val;
this.next = null;
}
}
class Lists {
constructor(){
this.head = null;
this.tail = null;
this.length = 0;
}
push(value) {
const newNode = new Node(value);
if(!this.head) {
this.head = newNode;
this.tail = newNode;
} else {
this.tail.next = newNode;
this.tail = newNode;
}
this.length++;
return this;
}
pop() {
if(!this.head) return undefined;
let current = this.head;
let newTail = current;
while(current.next) {
// current.next에 값이 있을 경우에만 loop
newTail = current;
current = current.next;
}
this.tail = newTail;
this.tail.next = null;
this.length--;
if(this.length === 0) {
this.head = null;
this.tail = null;
}
return current;
}
shift() {
if(!this.head) return undefined;
let current = this.head;
this.head = current.next;
this.length--
if(this.length === 0) this.tail = null;
return current;
}
unshift(value) {
const newNode = new Node(value);
if(!this.head) {
this.head = newNode;
this.tail = newNode;
} else {
newNode.next = this.head;
this.head = newNode;
}
this.length++;
return this;
}
get(index) {
if(index <= 0 || index >= this.length) return null;
let counter = 0;
let current = this.head;
while(counter !== index) {
current = current.next;
counter++;
}
return current;
}
set(index, val){
var foundNode = this.get(index);
if(foundNode){
foundNode.val = val;
return true;
}
return false;
}
insert(index, val) {
if(index < 0 || index > this.length) return false;
if(index === this.length) return !!this.push(val);
if(index === 0) return !!this.unshift(val);
var newNode = new Node(val);
var prev = this.get(index-1);
prev.next = newNode;
var temp = prev.next;
newNode.next = temp;
this.length++;
return true;
}
remove(index) {
if(index < 0 || index >= this.length) return undefined;
if(index === 0) this.shift();
if(index === this.length-1) this.pop();
var previousNode = this.get(index-1);
var removed = previousNode.next;
previousNode.next = removed.next;
return removed;
}
reverse(){
var node = this.head;
this.head = this.tail;
this.tail = node;
var next;
var prev = null;
for(var i = 0; i < this.length; i++){
next = node.next;
node.next = prev;
prev = node;
node = next;
}
return this;
}
print(){
var arr = [];
var current = this.head
while(current){
arr.push(current.val)
current = current.next
}
console.log(arr);
}
}
</div>
</details>
```js
class Node{
constructor(val) {
this.val = val;
this.next = null;
}
}
class Lists {
constructor(){
this.head = null;
this.tail = null;
this.length = 0;
}
push(value) {
const newNode = new Node(value);
if(!this.head) {
this.head = newNode;
this.tail = newNode;
} else {
this.tail.next = newNode;
this.tail = newNode;
}
this.length++;
return this;
}
pop() {
if(!this.head) return undefined;
let current = this.head;
let newTail = current;
while(current.next) {
// current.next에 값이 있을 경우에만 loop
newTail = current;
current = current.next;
}
this.tail = newTail;
this.tail.next = null;
this.length--;
if(this.length === 0) {
this.head = null;
this.tail = null;
}
return current;
}
shift() {
if(!this.head) return undefined;
let current = this.head;
this.head = current.next;
this.length--
if(this.length === 0) this.tail = null;
return current;
}
unshift(value) {
const newNode = new Node(value);
if(!this.head) {
this.head = newNode;
this.tail = newNode;
} else {
newNode.next = this.head;
this.head = newNode;
}
this.length++;
return this;
}
get(index) {
if(index <= 0 || index >= this.length) return null;
let counter = 0;
let current = this.head;
while(counter !== index) {
current = current.next;
counter++;
}
return current;
}
set(index, val){
var foundNode = this.get(index);
if(foundNode){
foundNode.val = val;
return true;
}
return false;
}
insert(index, val) {
if(index < 0 || index > this.length) return false;
if(index === this.length) return !!this.push(val);
if(index === 0) return !!this.unshift(val);
var newNode = new Node(val);
var prev = this.get(index-1);
prev.next = newNode;
var temp = prev.next;
newNode.next = temp;
this.length++;
return true;
}
remove(index) {
if(index < 0 || index >= this.length) return undefined;
if(index === 0) this.shift();
if(index === this.length-1) this.pop();
var previousNode = this.get(index-1);
var removed = previousNode.next;
previousNode.next = removed.next;
return removed;
}
reverse(){
var node = this.head;
this.head = this.tail;
this.tail = node;
var next;
var prev = null;
for(var i = 0; i < this.length; i++){
next = node.next;
node.next = prev;
prev = node;
node = next;
}
return this;
}
print(){
var arr = [];
var current = this.head
while(current){
arr.push(current.val)
current = current.next
}
console.log(arr);
}
}class Node {
constructor(val) {
this.val = val;
this.next = null;
this.prev = null;
}
}
class DoublyLinkedList {
constructor() {
this.head = null;
this.tail = null;
this.length = 0;
}
push(val) {
const newNode = new Node(val);
if(!this.head) {
this.head = newNode;
this.tail = newNode;
} else {
this.tail.next = newNode;
// 1 - > 100
newNode.prev = this.tail;
// 100 - > 1
this.tail = newNode;
}
this.length++;
return this;
}
pop() {
if(!this.head) return undefined;
let poppedNode = this.tail;
// return 값을 위해 필요한 부분
if(this.length === 1) {
this.head = null;
this.tail = null;
} else {
this.tail = this.tail.prev;
this.tail.next = null;
}
this.length--;
return poppedNode;
}
shift() {
if(!this.lnegth) return undefined;
let oldHead = this.head;
if(this.length === 1) {
this.head = null;
this.tail = null;
} else {
this.head = this.head.next;
this.head.prev = null;
oldHead.next = null;
}
this.length--;
return oldHead;
}
unshift(val) {
const newNode = new Node(val);
if(!this.head) {
this.head = newNode;
this.tail = newNode;
} else {
this.head.prev = newNode;
newNode.next = this.head;
this.head = newNode;
}
this.length++;
return this;
}
get(index) {
if(index < 0 || index >= this.length) return null;
let count;
let searched;
if(index <= this.length/2) {
searched = this.head;
count = 0;
while(count !== index) {
searched = searched.next;
count++;
}
} else {
searched = this.tail;
count = this.length - 1;
while(index !== index) {
searched = searched.prev;
count--;
}
}
return searched;
}
set(index, value) {
// this.get(index).val = value;
let foundNode = this.get(index);
if(foundNode !== null) {
foundNode.val = value;
return true;
} else return false;
}
insert(index, value) {
if(index < 0 || index >= this.length) return false;
if(index === 0) return !!this.unshift(value);
if(index === this.length) return !!this.push(value);
const newNode = new Node(value);
const beforedNode = this.get(index-1);
const afterNode = this.get(index+1);
beforedNode.next = newNode, newNode.prev = beforedNode;
newNode.next = afterNode, afterNode.prev = newNode;
this.length++;
return true;
}
remove(index) {
if(index < 0 || index >= this.length) return undefined;
if(index === 0) return this.shift();
if(index === this.length-1) return this.pop();
const foundNode = this.get(index);
const beforeNode = this.get(index-1);
const afterNode = this.get(index+1);
beforeNode.next = afterNode, afterNode.prev = beforeNode;
foundNode.next = null, foundNode.prev = null;
this.length--;
return foundNode;
}
}
const dll = new DoublyLinkedList();
dll.push(1);
dll.push(2);
dll.push(3);
dll.unshift(4);
console.log(dll.get(3));시간복잡도 정리
UDEMY의 javascript datastructure 강의를 듣고 정리한 내용입니다.
http://otter-log.world 로 이사했어요!