S E P H ' S

연결리스트 덱 (LinkedList Deque) 배열 덱 다음으로 다루려고 했던 내용이었는데 힙을 급하게 정리해봐야 할 필요가 있어서 힙 다음 순서로 연결리스트 덱을 다루게 됐다. 기본적으로 양방향 연결리스트, 더블 링크드리스트의 개념을 그대로 사용한다. 배열 덱에서와 마찬가지로 구조를 다시한번 짚고 넘어가자. 배열과 다르게 연결리스트를 사용하기 때문에 index로 관리되는 것이 아니라 node 단위로 구성된 객체를 서로 연결하여 구성되어 있다. 양방향 연결리스트를 바탕으로 구현될 것이기 때문에 구조를 다시 한번 보자. 노드는 노드의 데이터, 이전 노드, 다음 노드를 가리키는 변수들을 갖고 있다. 또한 구조는 offer는 기본적으로 offerLast 즉, 마지막에 더해지며 첫번째에 삽입할 수 있는 off..

Heap (Using Array) '우선순위 큐'가 힙 자료구조를 이용하여 구현되기 때문에 힙을 다뤄보려고 한다. 힙은 '최솟값 또는 최댓값을 빠르게 찾아내기 위해 완전이진트리 형태로 만들어진 자료구조'다. 먼저 완전이진트리를 이해해야 한다. 기본적으로 트리의 구조를 먼저 이해해보자. 위의 이미지 같은 자료구조를 Tree 구조라고 한다. 트리에 대해 더 자세히 알아보자 부모노드(parent node) : 자기 자신(노드)과 연결된 노드 중 자신보다 높은 노드를 의미 자식노드(child node) : 자기 자신(노드)과 연결된 노드 중 자신보다 낮은 노드를 의미 루트노드(root node) : 뿌리 노드라고도 하며 루트 노드는 하나의 트리에선 하나만 존재하고 부모 노드가 없다. 최상위 노드이다. 단말노드(..

Deque (Using Array) Deque는 Double-ended queue의 줄임말이다. 두 개의 종료지점이 있는 queue라는 뜻이다. 덱의 장점은 스택처럼 사용할 수도 있고 큐처럼 사용할 수 있는 자료구조이다. 덱의 구조를 큐의 구조와 한번 비교해보자 Deque는 삽입, 삭제가 총 12 종류가 있다. offer 계열과 poll 계열의 경우 삭제 과정에서 저장공간이 넘치거나 삭제할 원소가 없을 때 특정 값(null, false 등)을 반환하지만, add 계열과 remove 계열은 예외를 던진다. ArrayDeque 구현 클래스 및 생성자 구성 resize 메소드 구현 offer 계열 메소드 구현 poll 계열 메소드 구현 peek 계열 메소드 구현 size, isEmpty, contains, c..

Queue (Using LinkedList) 7. 배열 큐(Array Queue) 와는 다르게 LinkedList를 기반으로 구현한다. 기본적으로 LinkedList에 대한 이해가 필요하다. 자바에서는 대중적으로 LinkedList로 구현한 큐를 많이 사용한다. 배열로 구현한 큐의 경우 내부에서 Object[] 배열을 담고 있기 때문에 요소가 들어있는 배열의 용량에 따라 resize()를 해주어야 하고 선형 큐로 구현한 경우 요소들이 뒤로 쏠리는 문제가 있기 때문에 이러한 문제를 효율적으로 극복하고자 원형으로 구현하는데 이 구현이 고려해야 할 점도 많고 복잡하다. 배열 대신 연결리스트로 구현할 경우 많은 단점들이 해결된다. 각 데이터들을 노드 객체에 담고 노드 간 서로 연결하기 때문에 배열처럼 요소 개수..