잠보

class Node {
	constructor(value) {
		this.value = value;
		this.next = null;
	}
}

class Deque {
	constructor() {
		this.head = null;
		this.tail = null;
		this.size = 0;
	}
	
	unshift(value) {
		if (this.head === null) {
			this.head = new Node(value);
			this.tail = this.head;
			this.size++;
			return;
		}
		
		let newNode = new Node(value);
		let current = this.head;
		
		this.size++;
		this.head = newNode;
		this.head.next = current;
	}
	
	shift() {
		if (this.head === null) return;
		if (this.head.next === null) {
			this.head = null;
			this.tail = null;
			this.size--;
			return;
		}
		
		this.size--;
		this.head = this.head.next;
	}
	
	push(value) {
		if (this.head === null) {
			this.head = new Node(value);
			this.tail = this.head;
			this.size++;
			return;
		}
		
		this.size++;
		this.tail.next = new Node(value);
		this.tail = this.tail.next;
	}
	
		pop() {
		if (this.head === null) return;
		if (this.head.next === null) {
			this.head = null;
			this.tail = null;
			this.size--;
			return;
		}
		
		let current = this.head;
		
		while(current.next.next) {
			current = current.next;
		}
		
		this.size--;
		current.next = null;
		this.tail = current;
	}
	
	isEmpty() {
		return this.head === null ? true : false;
	}
	
	get length() {
		return this.size;
	}

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

class Node {
	constructor(value) {
		this.value = value;
		this.next = null;
	}
}

class Queue {
	constructor() {
		this.head = null;
		this.tail = null;
		this.size = 0;
	}
	
	enqueue(value) {
		if (this.head === null) {
			this.head = new Node(value);
			this.tail = this.head;
			this.size++;
			return;
		}
		
		this.size++;
		this.tail.next = new Node(value);
		this.tail = this.tail.next;
	}
	
	dequeue() {
		if (this.head === null) return;
		if (this.head.next === null) {
			this.head = null;
			this.tail = null;
			this.size--;
			return;
		}
		
		
		this.head = this.head.next;		
		this.size--;
	}
	
	isEmpty() {
		return this.head === null ? true : false;
	}
	
	get length() {
		return this.size;
	}

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

class Node {
	constructor(value) {
		this.value = value;
		this.next = null;
	}
}

class Stack {
	constructor() {
		this.head = null;
		this.tail = null;
		this.size = 0;
	}
	
	push(value) {
		if (this.head === null) {
			this.head = new Node(value);
			this.tail = this.head;
			this.size++;
			return;
		}
		
		this.size++;
		this.tail.next = new Node(value);
		this.tail = this.tail.next;
	}
	
	pop() {
		if (this.head === null) return;
		if (this.head.next === null) {
			this.head = null;
			this.tail = null;
			this.size--;
			return;
		}
		
		let current = this.head;
		
		while(current.next.next) {
			current = current.next;
		}
		
		this.size--;
		current.next = null;
		this.tail = current;
	}
	
	isEmpty() {
		return this.head === null ? true : false;
	}
	
	peek() {
		if (this.head === null) return;
		
		return this.tail.value;
	}
	
	get length() {
		return this.size;
	}
    
    clear() {
		this.head = null;
		this.tail = null;
		this.size = 0;
	}
}

연결리스트란?

연결리스트란 여러개의 노드를 연결함으로써 데이터를 보관하는 자료구조로 노드는 데이터를 가진 data 부분과 다음 노드를 연결하는 

link 부분으로 나뉘어져 있다.

연결리스트의 장점

1. 배열과는 다르게 필요한 만큼 메모리를 동적으로 할당 받아서 사용한다. 즉, 데이터 삽입 시에만 메모리 추가 사용하므로 효율적.
2. 삽입 삭제가 간단하다 : 새로운 노드 삽입 삭제 시 포인터 값(link)만 변경해주면 되기 때문이다.

연결리스트의 단점

1. 노드 접근이 배열보다 오래 걸린다 : 첫 노드부터 순차적으로 접근해야하기 때문이다. 메모리 구조상 차이.
2. 물리적으로 인접한 메모리에 위치해있지 않다 : 배열과 달리 포인터로 다음 노드의 위치를 알 수 있으므로 메모리 주소 공간이 떨어져있다.
3. 참조 포인터를 위한 메모리 공간이 낭비된다.

연결리스트의 시간복잡도

※ 중간 삭제 삽입 시 해당 위치의 전과 후의 데이터에 접근해야하고 작업을 해야하므로 O(n + 1)이 걸린다. 위의 삽입 삭제 상수시간은 접근을 고려하지 않고 삽입 삭제만 봤을 때의 시간이다.

연결리스트의 종류

1. 단일 연결리스트 : 가장 기본적인 연결리스트로 마지막 노드는 가리키는 노드가 없다. 보통 스택 구현에 많이 사용. 마지막 노드가 null을 가르킨다.
2. 이중 연결리스트 : 노드를 연결하는 link가 앞 뒤로 존재해서 앞 뒤 노드들 간의 관계를 바로 알 수 있다. 보통 큐 구현에 많이 사용. 단일 연결리스트는 헤드노드 유실시 전체 자료를 다 잃어버리지만 이중 연결리스트는 헤드만 아닌 테일 노드도 가지고 있으면 복구가 가능하다 또한 단일 연결리스트는 헤드에서만 탐색이 가능하나 이중 연결리스트는 테일에서도 탐색이 가능하므로 탐색의 방향이 바뀌어야 하는 경우 사용한다. 현실에서 사용하는 연결 리스트는 대부분 이중 연결리스트라고 보면 된다.
3. 원형 연결리스트 : 마지막 노드가 다시 처음 노드를 가리키는 연결리스트. 헤드와 테일의 구분이 없다. 스트림 버퍼의 구현에 많이 사용.

※ 물론 위의 연결리스트 구현될 수 있다는 스택, 큐 등 자료구조는 배열로도 큐를 단일 연결리스트로도 구현 가능하다 해당 자료구조만큼보다는 조금 비효율적이다라는 것이다.

배열과 연결리스트 사용 의문과 결론

동적배열과 연결리스트의 이 2개의 글을 읽어보셨으면 아시겠지만 결국 시간복잡도만 봤을 때 배열과 연결리스트는 데이터 접근과 탐색(탐색은 빅오 표기법은 같으나 메모리를 생각했을 때 조금의 차이)을 제외하면 별 다른 점이 없다. 

결국 자료구조의 설계를 기준으로 결정해야하는데 연결리스트는 마지막 노드에 한 해 데이터 추가 삭제 시 상수 시간이 걸리는 점을 생각 동적 배열은 마지막에 데이터를 추가 삭제 시 분할 상환할 경우에 상수 시간이 걸리다는 점과 데이터의 접근과 탐색을 생각하면 될 것 같다.

또한 보통 개발자가 배우기를 연결리스트는 삽입, 삭제에 유리, 배열은 접근 탐색에 유리하다는 것을 알고있다는 점도 반영.

결론은 데이터 접근, 탐색이 중요하면 배열을 사용. 데이터의 추가 삭제가 중요하면 연결리스트를 사용.

하지만 실무에서는 대부분 동적배열을 애용한다?!

배열이란?

배열이란 연관된 데이터를 하나의 변수에 그룹핑해서 관리하기 위한 방법이다. 

즉, 배열은 하나의 변수에 여러 정보를 담을 수 있어 많은 정보를 효율적으로 처리할 수 있는 자료구조이다.

배열의 장점

1. 검색 성능이 좋다 : 인덱스를 이용한 무작위 접근이 가능하므로 빠르다.
2. 순차 접근의 경우에도 데이터를 하나의 연속된 메모리 공간에 할당하므로 연결 리스트보다 빠르다.

배열의 단점

1. 자료의 삽입과 삭제에 비효율적이다 : 항목의 모든 요소를 이동시켜야해서 비효율적.
2. 메모리 공간 낭비 : 배열은 메모리를 할당 받아 사용하기 때문에 데이터의 존재 유무와 상관없이 일정한 크기의 공간을 점유하고 있기 때문에 데이터를 삭제하더라도 배열 자체를 제거하지 않은 이상 낭비를 유발한다.

배열의 시간복잡도

※ 배열의 마지막 원소에 삽입, 삭제 삽입은 당연히 간단하게 끝내지만 (상수 시간) 아닌 경우. 즉, 시간 복잡도의 평균과 최악을 가정하여O(n)이라고 생각하면 될 것 같습니다.

Array과 ArrayList의 차이점

Array

- 통상적으로 말하는 자료구조 상의 배열.

- 고정 배열.

- 배열의 크기를 지정하며 그 크기 이상 데이터 삽입 시 불가.

- 배열의 사용하지 않는 인덱스가 있더라도 고정 크기이므로 메모리 낭비.

ArrayList

- 동적 배열.

- 자동적으로 크기가 지정되며 그 크기 이상 데이터 삽입 시 원래 크기의 1.5 ~ 2배 사이즈로 크기가 확장되며 삽입 가능.

- 배열의 사용하지 않는 인덱스가 있을 시 크기가 줄어들며 만약 인덱스 1의 데이터를 삭제 시 고정 배열은 1에 접근하였을 때 데이터가 
없지만 동적 배열은 1에 접근하였을 때 2에 있던 데이터가 1로 가있어 데이터가 있다.

- Hash Map, Dictionary, Linked List로 구현되어 있다.

코드 예시

// 자바스크립트의 배열은 다른 데이터 타입을 배열안에 같이 넣을 수 있다.
// 다트의 배열은 타입 지정이 없을 시 다른 데이터 타입을 배열안에 같이 넣을 수 있다.

javascript

고정 배열
1. let arr = new Array(3);

동적 배열
1. let arr = [];
2. let arr new Array();