CS/자료구조

List, Set, Map 각각의 특성

List 순서가 있고 중복을 허용하는 자료구조. 인덱스로 원소 접근, 원소 삽입, 원소 삭제가 가능하다. 크기가 가변적이고, 이에 따라 비어있는 공간이 없다. 원하는 데이터를 찾을 때 최악의 경우 O(n) 시간이 걸릴 수 있다. Set 순서가 없고 중복을 허용하지 않는 자료구조. 인덱스가 존재하지 않아서 반복자를 사용한다. 탐색이 빠르다. 정렬 되어 있을 시 O(log n) Map 순서가 없는 {Key, Value} 쌍으로 이루어진 자료구조. Key는 중복을 허용하지 않지만 Value는 중복이 가능하다. 인덱스가 존재하지 않아서 반복자를 사용한다. 탐색이 빠르다. 정렬 되어 있을 시 O(log n)

[자료구조]3. 큐

Queue ADT, 큐 추상자료형 큐는 FIFO(First In, First Out), 선입선출 구조이다. 먼저 들어온 원소가 먼저 나간다. 원소의 삽입은 큐의 뒤에서 이루어지고, 원소의 삭제는 큐의 앞에서 이루어진다. 큐의 주요 기능은 다음과 같다. enqueue(obj) : 큐의 뒤(rear)에 원소를 삽입한다. dequeue(obj) : 큐의 앞(front)에 있는 원소를 꺼낸다. 큐의 추가적인 기능은 다음과 같다. front/top : 꺼내지 않고 큐의 맨 앞의 원소를 확인한다. size : 큐에 저장된 원소의 수를 return한다. empty : 큐가 비어있는지 확인한다. 예외처리는 QueueEmpty로 큐가 빈 상태인지 확인한다. 큐의 구현으로는 배열 혹은 링크드 리스트를 사용할 수 있다. 큐..

[자료구조]2. 스택

STACK ADT, 스택 추상자료형 스택 추상자료형은 필요한 타입에 맞는 정보를 저장한다. 삽입과 삭제가 후입선출 구조로 이루어진다. 스택의 주요 기능은 다음과 같다. push(object) : element를 삽입한다. pop() : 마지막으로 push된 element를 꺼낸다(return하고 삭제한다). 스택의 추가적인 기능은 다음과 같다. top() : 마지막으로 push된 element를 보여준다. size() : 저장된 elements의 수를 알려준다. empty() : 스택이 비어있는지 확인한다. 예외 처리에서는 pop()과 top() 메서드를 사용할 때 Stack Empty 예외처리를 사용한다. Stack을 사용한 프로그램 예시에는 다음이 있다. 웹 브라우저 방문 기록 텍스트 편집기 되돌리기..

[자료구조]1. 단일 링크드 리스트, 단일 연결 리스트

자료구조란 쉽게 말해, 데이터를 저장하고 사용하기 위해 만드는 것이다. 세 가지 기본기능으로는 탐색(Search), 삽입(Insert), 삭제(Delete)가 있다. 자료구조는 구현방법과 성능분석이 중요하다. 링크드 리스트의 특징 (배열과 비교) 배열은 주소가 연속적이지만, 링크드 리스트는 주소가 연속적이지 않다. 배열은 크기가 고정이므로 공간이 부족하거나 낭비될 수 있지만, 링크드 리스트는 크기가 가변적이므로 부족, 낭비가 없다. 배열에 비해 접근이 느리고 구현도 어렵다. 단일 링크드 리스트 단일 링크드 리스트는 node가 순차적으로 이루어져 있다. 각 노드는 값을 나타내는 element 부분과 다음 node를 가리키는 주소(포인터)로 구성된다. 맨 앞 노드를 Head라고 가리키고 맨 뒤 노드를 Tai..