on
stack, queue, linked list
카테고리 설명
연결리스트는 각각의 노드가 다음 노드와 단방향으로 연결되어 있는 자료구조이다.
따라서 검색을 할 경우 모든 노드를 순차적으로 순회하며 검색하게 되고(시간 복잡도 N),
맨 앞 또는 삽입, 삭제 할 경우, 또 맨 앞에 삽입할 경우만 상수의 시간 복잡도이며, 맨 뒤 노드의 제거시 모든 노드를 밟고 올라가야 하기때문에 시간 복잡도는 N이 된다.
index(몇 번째에) 접근 또한 노드를 순차적으로 순회하며 올라가야 하기때문에 검색과 같은 시간 복잡도 N을 가지게 된다.
중간에 삽입하거나 삭제할 경우 접근과 마찬가지의 로직을 돌기때문에 N 시간 복잡도를 가지게 된다.
이중 연결리스트는 각 노드가 단방향으로 연결된 것이 아니라 양방향으로 연결되어 있는 자료구조이다.
단일 연결리스트와 다르게 마지막 노드 삭제시 직전 노드로 바로 돌아갈 수 있으므로 마지막 노드를 지우는것도 상수의 시간 복잡도를 가진다.
또 index를 통한 접근도 만약 그 숫자가 전체를 기준으로 절반에서 뒤쪽에 있다면 뒤부터, 앞에 있다면 앞에서부터 조회해서 이동할수 있기 때문에 2/n 시간 복잡도이지만 결국엔 n시간 복잡도라고 말할 수 있다. 다만 단일 연결리스트보다는 빠르다!
다만, 이중 연결리스트는 이전 노드와의 연결도 메모리에 저장해야하기 때문에 단일 연결리스트보다 더 많은 메모리를 사용한다는 점을 기억하자!
스택의 경우 후입 선출의 구조이다.
자바스크립트 내장 배열을 사용하는 경우, push와 pop을 이용하여 만든다.
만약에 shift,unshift를 사용하게되면 배열 안의 요소의 인덱싱이 하나씩 밀리고, 앞으로 당겨지기때문에 시간복잡도가 N이 되게 된다.
단일 연결리스트와 이중 연결 리스트로 스택을 구현할 수 있지만, 단일 연결 리스트로 구현할 경우, 뒤에 추가, 제거를 할 경우엔 시간 복잡도가 2N이 됨으로, 차라리 맨 앞에 추가하고 맨앞에서 제거하는 방식으로 하면 시간 복잡도가 상수가 됨으로 더 좋다.
큐의 경우 먼저 삽입된 요소가 먼저 나가는 선입선출의 구조이다.
단일, 이중 연결리스트로 구현할 수 있으나, 메모리 측면에서도 단일 연결리스트를 사용하는 것이 좋다.
단일연결리스트로 큐를 만들 경우, 시간 복잡도를 최소화 하기 위해 마지막 노드에 추가하고, 처음 노드를 삭제하는 방식으로 만드는 것이 좋다. 이럴 경우 시간 복잡도는 상수 값이 된다.