서비스, 어플리케이션에서 필요한 데이터를 효율적인 구조로 저장해놓기 위해 필요한 지식으로, 필요한 데이터에 가장 빠르고 효율적으로 접근할 수 있도록 하는 것이 목적이다.자료구조 학습 시 해당 자료구조의 다음의 네 가지를 point로 학습한다.1\. Order : 자료구
데이터를 인덱스에 대응시켜 나열한 자료구조같은 종류의 데이터를 관리하기 위해 사용한다.데이터를 순차적으로 저장한다.길이가 정해져 있다.
큐 (Queue) 큐란? > 큐의 특징 > FIFO(First-In, First-Out), LILO(Last-In, Last-Out) 줄을 서는 행위와 유사하다. > input|-|-|output -|-|-|- 1|-|-|- > input|-|-|output -|-
LIFO(Last-In, First-Out), FILO(First-In, Last-Out)가장 나중에 쌓은 데이터를 가장 먼저 빼낸다.데이터를 한쪽 끝에서만 넣거나 뺄 수 있다.cf)push : 스택에 데이터를 넣는 행위pop : 스택에서 데이터를 빼는 행위구조가 단순
배열의 한계를 극복하기 위한 자료구조노드(하나의 데이터) 생성 시, 데이터와 다음 데이터의 주소를 담을 공간을 만든다. \- 노드(Node) : 데이터의 저장 단위로 데이터 값과 포인터로 구성된다.포인터(Pointer) : 각 노드 안에서, 이전 또는 다음 노드와의
삽입할 노드의 이전 노드의 '다음 노드 주소'에 삽입할 노드의 주소를 넣어준다.삽입할 노드의 '다음 노드 주소'에 다음 노드의 주소를 넣어준다.삭제할 노드의 주소를 담고 있는 이전 노드의 '다음 노드 주소'에 삭제할 노드의 다음 노드의 주소를 넣어준다.
하나의 노드에 이전 데이터를 가리키는 포인터와 데이터, 이후 데이터를 가리키는 포인터로 이루어져있다.single linked list는 head에서부터 순차적으로 검색해야하지만, double linked list의 경우 head 또는 tail에서부터 검색할 수 있으므로
이전 노드의 next pointer에 추가할 노드의 주소를 넣어주어야 하고,추가할 노드의 before pointer에 이전 노드의 주소를 넣어주어야 한다.이후 노드의 before pointer에 추가할 노드의 주소를 넣어주어야 하고,추가할 노드의 next pointer
키(Key)와 값(value)를 매핑할 수 있는 데이터 구조이다.hash function에 key를 입력하면 주소를 리턴받아 value를 저장할 수 있다. \- 해쉬 함수(Hash Function) : 임의의 데이터를 고정된 길이의 값으로 리턴해주는 함수 \- 해쉬
데이터의 저장/읽기 속도가 빠르다. (검색 속도가 빠르다.)해쉬는 키에 대한 데이터가 있는지 중복에 대한 확인이 쉽다.일반적으로 hash function이 생성할 수 있는 주소에 대한 공간을 미리 할당하여야하므로, 저장 공간이 비교적 많이 필요하다.여러 키에 해당하는
Node와 Branch를 이용하여, 사이클을 이루지 않도록 구성한 데이터 구조이다.이진 트리(Binary Tree)의 경우 탐색 알고리즘 구현에 많이 사용된다. \- 최대 2개의 Branch를 갖는다.Node : 데이터와 브랜치 정보를 저장Root Node : 최상단
이진 탐색 트리의 구조를 생각하며 케이스 별로 풀어나가면 비교적 쉽게 생각해낼 수 있다.parent Node의 왼쪽 branch에는 자신보다 작은 수가 연결되어야하고, 오른쪽 branch에는 자신보다 큰 수가 연결되어야 한다.
Double Ended Queue, 양쪽 끝에서 삽입과 삭제가 가능하다.원소의 추가가 O(1)원소의 제거가 O(1)제일 앞/뒤의 원소 확인이 O(1)제일 앞/뒤가 아닌 나머지 원소들의 검색/변경은 원칙적으로 불가하다.
트리 (Tree) - 2 이진 탐색 트리 노드 삭제 1. Leaf Node 삭제 > 삭제할 Node의 Parent Node가 삭제할 Node를 가리키지 않도록 한다. 2. Child Node가 하나인 Node 삭제 > 삭제할 Node의 Parent Node가 삭제