자료구조

Deque

Deque의 특징 양방향 큐라고도 불리는 덱(Double-ended queue: Deque)은 맨 앞과 맨 끝, 양 쪽에서 요소의 삽입/삭제가 가능한 자료구조이다. 덱은 맨 끝으로만 요소 삽입이 가능했던 스택과 큐의 단점을 보완하고, 맨 뒤의 요소만 반환(삭제) 가능했던 스택, 맨 앞의 요소만 반환(삭제) 가능했던 큐의 기능을 통합한 자료구조이다. Deque의 구현 방법 큐와 마찬가지로 덱도 배열 또는 연결리스트로 구현 가능하다. 주의할 점은 단방향 연결리스트가 아닌, 양방향 연결리스트로 구현한다는 것이다. 그리고 큐가 그랬던 것 처럼, 배열이 아닌 연결리스트로 구현하는 것이 더 편리하다. 배열로 큐를 구현할 경우, 저장될 요소의 개수에 따라 배열의 크기를 동적으로 조정해주는 작업이 필요하다. 요소의 추..

Stack

스택의 특징 스택은 후입선출(Last in First out: LIFO)의 특징을 가진 자료구조이다. 후입선출이란 '나중에 들어온 것이 먼저 나간다'는 의미이다. 서 있는 긴 원통을 생각해보자. 여러 개의 원형 블럭을 원통에 넣는다. 그리고 원통에서 블럭을 하나 빼보자. 그 블럭은 가장 마지막에 들어간 블럭이다. 이것이 후입선출의 예시이며, 스택은 후입선출로 데이터를 관리한다. 스택은 대표적으로 페이지 뒤로가기, 실행 취소, 수식 괄호 검사 등에 사용된다. 스택 구현 스택 인터페이스 구현부 public interface StackInterface { /** * 스택의 최상단에 요소를 추가한다. * @param element: 스택에 추가할 요소 * @return 스택에 추가된 요소 */ T push(T ..

DoubleLinkedList

DoubleLinkedList 특징 DoubleLinkedList는 LinkedList의 단점을 보완한 자료구조이다. DoubleLinkedList는 이중 연결 리스트 또는 양방향 연결 리스트라고 불리는데, 이름처럼 다음 노드 뿐만 아니라, 이전 노드에 대해서도 참조하는 노드를 사용하여 데이터를 저장한다. LinkedList는 다음 노드를 참조하는 노드를 사용하고, DoubleLinkedList는 다음 노드 뿐만 아니라 이전 노드도 참조하는 노드를 사용하는 것 외에는 차이가 없다. 사용하는 노드의 차이가 어떤 이점을 가져오는 것일까? LinkedList에 10개의 데이터가 저장되어있다고 가정하자. LinkedList의 노드는 다음 노드만을 참조하고 있기 때문에, 9번째 노드에 접근하기 위해서는 head(..

LinkedList

ArrayList는 크기를 변경할 수 없고(사실 저장 공간은 크기가 정적인 배열이며, 저장 공간이 부족할 경우 새로 배열을 생성한다), 시작 또는 중간 데이터의 추가/삭제 시 속도면에서 비효율적이라는 단점이 있다. LinkedList는 ArrayList의 단점을 보완한 자료구조이다. LinkedList의 특징 LinkedList는 특정한 저장 공간에 데이터를 저장하지 않는다. 노드(Node)라는 객체를 통해 데이터를 저장한다. 노드는 데이터와 다음 노드에 대한 참조로 구성되어있다. 다음 노드에 대한 참조를 통해 노드들은 연결된다. 첫 번째 노드를 head, 마지막 노드를 tail이라고 부른다. 노드가 1개일 경우, head와 tail은 동일한 노드이다. LinkedList 객체는 첫 번째 노드를 참조하는..

ArrayList

ArrayList는 원소의 중복을 허용하면서, 저장 순서를 유지할 수 있는 선형 자료구조이다. ArrayList의 특징 ArrayList의 특징을 살펴보면서 ArrayList를 이해해보자. ArrayList는 크기가 고정적이고, 데이터의 추가/제거가 번거롭다는 배열의 단점을 보완한 선형 자료구조이다. ArrayList는 내부에 갖고 있는 Object[]을 이용해 데이터를 저장한다. ArrayList는 크기가 가변적이다. 사실 Object[]에 데이터를 저장하기 때문에 크기는 정해져있다. 다만 기존 크기를 초과하여 데이터를 추가할 경우, 더 큰 Object[]를 생성하고 기존 배열의 데이터를 복사하여 사용한다. ArrayList.size()는 Object[]의 크기가 아닌, 마지막 데이터의 인덱스를 반환하..

2차원 배열

1차원 배열은 int, double, String 등 다양한 타입의 데이터를 원소로 가질 수 있다. 2차원 배열은 이러한 1차원 배열을 원소로 갖는 또 하나의 배열이라고 할 수 있다. 이 글에서는 1차원 배열을 원소로 갖는 배열을 외부 배열, 원소로 담기는 1차원 배열을 내부 배열이라고 지칭하겠다. 2차원 배열의 선언 2차원 배열은 int[][] ints = new int[3][3];처럼 선언할 수 있다. 앞의 [3]은 외부 배열의 길이, 뒤의 [3]은 내부 배열의 길이를 의미한다. 외부 배열의 길이만 먼저 선언하고, 내부 배열의 길이는 나중에 선언해도 된다. 일반적인 1차원 배열에서 배열의 길이만 지정하고 원소를 나중에 저장해도 됐듯이, 2차원 배열에서도 원소를 담는 외부 배열의 길이만 지정하고 원소인..