연결리스트는 데이터를 링크로 연결해서 관리하는 자료구조다. 자료의 순서는 정해져 있지만 메모리상의 연속성은 보장되지 않는다. 데이터를 담고 있는 노드들이 연결되어 있고, 노드의 포인터가 이전, 다음 노드와의 연결을 담당한다. 연결리스트에서 사용되는 용어는 다음과 같다. node : 데이터 저장 단위로 값과 포인터로 구성된다.(내부 부품이기에 외부에 노출되지 않는것이 좋다. private) pointer : 다음 노드나 이전 노드의 연결 정보(다음 혹은 이전 노드의 주소(정보)값)(Next) head : 가장 처음에 위치하는 노드를 일컫는다. tail : 가장 마지막에 위치하는 노드를 일컫는다. 노드를 가리키는 포인터는 C에서는 포인터변수가 있었지만 여기서는 그냥 같은 타입으로 해서 연결해주면 된다. no..
Map은 키(Key)와 값(Value) 으로 이루어진 Entry객체 데이터를 보관하는 자료구조이다. java.util안에 존재한다. 순서를 유지하지 않는다. Key는 중복을 허용하지 않지만, Value는 가능하다. 해시 맵(HashMap) Map 인터페이스를 구현한 대표적인 Map 컬렉션이다. Map은 키와 값으로 구성된 Entry객체를 저장하는 구조를 가지고 있는 자료구조이다. 여기서 키와 값은 모두 객체이다. 값은 중복 저장될 수 있지만 키는 중복 저장될 수 없다. 만약 기존에 저장된 키와 동일한 키로 값을 저장하면 기존의 값은 없어지고 새로운 값으로 대치된다. HashMap은 이름 그대로 해싱(Hashing)을 사용하기 때문에 특정 데이터의 저장위치를 해시함수를 통해 바로 알 수 있기 때문에 데이터..
배열(Array) 많은 수의 데이터를 다룰 때 사용하는 자료구조다. 각 데이터를 인덱스와 1:1 대응하도록 구성한다. 데이터가 메모리 상에서 연속적으로 저장된다.(연결리스트는 아니다.) 배열의 장점 - 인덱스를 이용하여 데이터에 빠르게 접근이 가능하다. 배열의 단점 - 미리 최대길이를 정해서 생성해야한다. 가변길이배열은 배열 크기를 변형할 때마다 새로운 배열을 만들어줘야한다. 배열 시간복잡도 ( Big O ) 삽입(Insertion) - O(1)(인덱스를 알 때 or 단순 add) / O(n) (인덱스를 모를 때 or 특정 데이터 삽입 시) 제거(remove) - O(1)(인덱스를 알 때 or 단순 remove) / O(n) (인덱스를 모를 때 or 특정 데이터 제거 시) 접근(access) - O(1)..
선형 큐(Queue) 컴퓨터의 기본 선형 자료구조 중 하나로 FIFO(First In First Out), 선입선출의 특징을 갖는다. 기본적으로 데이터 추가(Enqueue), 꺼내기(Dequeue), 큐 공간 확인 동작으로 이루어진다. 한쪽 끝을 front, 반대쪽 끝을 rear라고 할 때, rear로 데이터가 추가되고, front에서 데이터가 꺼내진다. 큐 오버플로우(Overflow), 언더플로우(Underflow) 오버플로우 - 큐 크기만큼 데이터가 꽉 차서 더이상 들어가지 않을 때 언더플로우 - 큐가 비어있는데 데이터를 꺼내려고 하는 경우 큐 사용처 입력 순서대로 데이터 처리가 필요할 때 사용한다. 프린트 출력 대기열 그래프 너비우선탐색(BFS - Breath First Search) 시간복잡도 (..
스택(Stack) 컴퓨터의 기본 선형 자료구조 중 하나로 LIFO(Last In First Out), 후입선출의 특징을 갖는다. 기본적으로 데이터 추가(Push), 꺼내기(Pop), 스택 공간 확인 동작으로 이루어진다. 가장 먼저 데이터가 들어온 위치를 Bottom, 가장 마지막에 데이터가 들어온 위치를 Top이라고 한다. 스택 오버플로우(Overflow), 언더플로우(Underflow) 오버플로우 - 스택 크기만큼 데이터가 꽉 차서 더이상 들어가지 않을 때 언더플로우 - 스택이 비어있는데 데이터를 꺼내려고 하는 경우 스택 사용처 데이터가 입력된 순서의 역순으로 처리되어야 할 때 함수 콜 스택(함수1 안에서 함수2 안에서 함수3을 호출했을 때, 함수3이 끝나고 다시 함수2로 넘어가고 함수2가 끝나고 다시..
