나작코

데크(Double-ended Queue; Deque)란 양쪽 끝에서 삽입과 삭제를 허용하는 자료구조입니다. 스택과 큐 자료구조를 혼합한 자료구조라고 할 수 있습니다. 예를 들어 스크롤, 문서 편집기 등의 undo 연산, 웹 브라우저의 방문 기록 등에 사용됩니다. 웹 브라우저 방문 기록의 경우, 최근 방문한 웹 페이지 주소는 앞에 삽입하고 일정 수의 새 주소들이 앞쪽에서 삽입되면 뒤에서 삭제가 수행됩니다. 데크를 배열이나 이중 연결 리스트로 구현한 경우, 스택과 큐의 연산 수행 시간과 같습니다. 하지만 양 끝에서 삽입과 삭제를 할 수 있으므로 프로그램이 복잡해집니다. 자바는 java.util 패키지에서 Deque 인터페이스를 제공하며 이는 Queue에서 상속됩니다. 주요 메소드 삽입 addFirst(): ..

큐(Queue)란 선입선출(FIrst In First Out; FIFO), 먼저 들어온 데이터가 먼저 나가는 구조입니다. 단방향에서의 삽입과 삭제가 가능한 스택과 달리, 삽입과 삭제가 양 끝에서 각각 수행되는 자료구조입니다. 관공서, 은행, 우체국, 병원 등에서 번호표를 이용한 줄서기가 대표적인 큐의 예시입니다. 큐는 선형 자료구조이므로 1차원 배열 또는 단순 연결 리스트로 구현합니다. 그러나 배열로 구현하는 경우 삽입과 삭제를 거듭하면 큐의 항목이 배열의 오른쪽 부분으로 편중되는 문제가 발생합니다. 새 항목은 뒤에 삽입되고 삭제는 앞에서 일어나기 때문입니다. 이를 해결하는 방법 중 하나는 큐의 항목을 배열의 앞부분으로 이동시켜 배열의 마지막 원소가 첫 원소와 맞닿아 있도록 구현하는 것입니다. 연결 리스..

스택(Stack)이란 후입선출(Last In First Out; LIFO), 즉 마지막에 들어온 데이터가 먼저 나가는 구조입니다. 데이터가 입력된 순서의 역순으로 처리되어야 할 때 사용합니다. 예를 들어 함수 콜 스택, 수식 계산, 인터럽트 처리 등이 있습니다. 데이터 추가, 꺼내기, 스택 공간 확인 동작으로 이루어집니다. 스택의 동작 예시 다음과 같습니다. ↓push() ↑pop() 3(3) 3(1) 2(2) 2(2) 1(1) 1(3) 일반 숫자는 원소, 괄호 안 숫자는 순서를 의미합니다. 예를 들어, push는 1, 2, 3 순서대로 원소가 삽입되었습니다. 그러나 pop으로 원소를 꺼내고자 할 때에는 3, 2, 1과 같이 삽입할 때의 역순으로 원소를 꺼내게 됩니다. 스택에서는 항목을 위에서 push하..

원형 연결 리스트(Circular Linked List)란 마지막 노드가 첫 노드와 연결된 단순 연결 리스트입니다. 마지막 노드의 레퍼런스가 저장된 last가 단순 연결 리스트의 head와 유사한 역할을 합니다. 여러 사람이 차례로 돌아가며 하는 게임을 구현하는 데 적합한 자료구조이며, 많은 사용자가 동시에 사용하는 컴퓨터에서 cpu 시간을 분할하여 작업에 할당하는 운영체제에도 쓰입니다. 이항 힙이나 피보나치 힙과 같은 우선순위 큐를 구현하는 데에도 원형 연결 리스트가 부분적으로 사용됩니다. 삽입이나 삭제 연산 각각 상수 개의 레퍼런스를 갱신하므로 O(1)시간에 수행됩니다. 탐색 연산은 단순 연결 리스트의 탐색과 같이 last로부터 노드들을 순차적으로 탐색해야 하므로 O(n) 시간이 소요됩니다. 원형 연..

이중 연결 리스트(Doubly Linked List)는 각 노드가 두 개의 레퍼런스를 가지고 각각 이전 노드와 다음 노드를 가리키는 연결 리스트입니다. 각 노드에 2개의 레퍼런스를 가지고 각각 이전 노드와 다음 노드를 가리키어 양방향 탐색이 가능합니다. 이중 연결 리스트는 단순 연결 리스트의 단점을 보완하지만, 노드마다 추가로 1개의 레퍼런스를 저장해야 하는 단점을 가집니다. 이중 연결 리스트에서 수행되는 삽입이나 삭제 연산은 각각 상수 개의 레퍼런스만을 갱신하므로 O(1) 시간에 수행된다. 탐색 연산은 단순 연결 리스트의 탐색과 같이 head 또는 tail로부터 노드들을 순차적으로 탐색해야 하므로 O(n) 시간이 걸립니다. 이중 연결 리스트의 장단점 장점 단순 연결 리스트와 달리, 양방향 탐색 가능 단..

단순 연결 리스트(Singly Linked List)란 동적 메모리 할당을 이용해 리스트를 구현하는 가장 간단한 형태의 자료구조입니다. 즉, 동적 메모리 할당을 받아 노드(Node)를 만들고, 노드는 레퍼런스를 이용하여 다음 노드를 가리키도록 만들어 노드들을 한 줄로 연결합니다. 노드마다 레퍼런스를 저장할 공간이 필요합니다. 각 노드 객체마다 항목을 저장할 item과 Node 레퍼런스를 저장하는 next를 가집니다. 자료의 순서는 정해져 있지만, 메모리상 연속성이 보장되지는 않습니다. 크기를 예측하지 않으므로 빈 공간이 존재하지 않습니다. 단순 연결 리스트는 이동방향이 단방향이기 때문에 다음 요소에 대한 접근은 쉽지만 이전 요소에 대한 접근은 어렵습니다. 이를 보완한 이중 연결 리스트(Doubly Lin..

배열(Array)은 동일한 타입의 원소들이 연속적인 메모리 공간에 할당되어 각 항목이 하나의 원소에 저장되는 기본적인 자료구조입니다. 특정 원소에 접근할 때에는 배열의 인덱스를 이용하여 O(1) 시간에 접근할 수 있습니다. 그러나 새 항목을 배열 중간에 삽입하거나 중간에 있는 항목을 삭제하면, 뒤따르는 항목들을 한 칸씩 뒤로 또는 앞으로 이동시켜야 하므로 삽입이나 삭제 연산은 항상 O(1) 시간에 수행할 수 없다. 배열은 이미 정해진 크기의 메모리 공간을 할당받은 뒤 사용해야 하므로, 빈자리가 없어 새 항목을 삽입할 수 없는 상황(Overflow)에 직면할 수도 있습니다. Overflow가 발생하면 에러 처리를 하여 프로그램을 정지시키는 방법이 주로 사용됩니다. 하지만 프로그램 안정성을 향상시키기 위해 ..

리스트(List)는 일련의 동일한 타입의 항목(item)들이 나열된 것을 의미합니다. 스택과 큐 자료구조도 리스트의 일종입니다. 일상에서는 학교의 학생 명단이나 시험 성적, 빌보드 차트, 버킷 리스트 등을 예로 들 수 있습니다. 여기서 말하는 리스트는 전문적 용어보다는, 앞서 설명한 데이터의 나열을 상징하는 표면적 단어로써의 의미가 큰 것 같습니다. 리스트와 관련된 기본 연산에는 k번째 항목을 읽는 접근, 임의의 항목을 찾는 탐색, 새 항목을 추가하는 삽입, 항목을 제거하는 삭제 연산이 있습니다. 이 책에서 리스트 파트에서는 배열, 단순 연결 리스트, 이중 연결 리스트, 원형 연결 리스트만을 담고 있습니다. ※ "자바와 함께하는 자료구조의 이해"라는 책을 참고하여 쓴 게시글입니다. 책에는 없는 내용을 추..

자료구조(Data Structure)는 일련의 동일한 타입의 데이터를 정돈하여 저장한 구성체입니다. 데이터를 정돈하는 목적은 프로그램에서 저장하는 데이터에 대해 접근, 탐색, 삽입, 삭제 등의 연산을 효율적으로 수행하기 위해서이며, 자료구조를 설계할 때는 데이터와 데이터와 관련된 연산을 함께 고려하여 설계해야 합니다. 자료구조의 효율성은 자료구조에 저장된 데이터에 대해 수행되는 연산의 수행 시간으로 측정합니다. 자료구조에 대한 연산 수행 시간 측정 방식은 알고리즘의 성능을 측정하는 방식과 동일합니다. 알고리즘의 성능은 수행 시간을 나타내는 시간 복잡도(Time Complexity)와 알고리즘이 수행되는 동안 사용되는 메모리 공간의 크기를 나타내는 공간 복잡도(Space Complexity)에 기반하여 분..