개발하는데 다 이유가 있겠지

자료구조(Data Structure)

1. 문자열

둘 이상의 결합된 문자

출처 : 사진 속 주소

• 불변성 : 기존 객체의 값을 바꾸는 것이 아닌 수정된 값을 가진 객체를 생성
• 문자열 끝에는 널 문자(종단문자, '\n') 반드시 들어감
  없다면 출력시 쓰레기값이 같이 출력됨

---

2. 배열

연속된 메모리 공간에 순차적으로 저장된 데이터 모음

작업	average case	worst case
접근(read)	O(1)	O(1)
삽입 및 추가(insert)	O(n)	O(n)
삭제(delete)	O(n)	O(n)
조회(search)	O(n)	O(n)

• 동일한 데이터 유형을 가짐
• 각 요소에 접근하는 시간은 O(1) => 인덱스로 바로 접근 가능
• 연속된 메모리에 단일 블록화하여 데이터 저장(낭비되는 공간이 적음)
• 삽입 및 삭제시 모든 요소를 움직여줘야 하기 때문에 비용이 많이 들게 됨 O(n)
• 물리적으로 데이터가 순차적으로 저장되기 때문에 순서와 index가 있으며, 인덱싱과 슬라이싱이 가능
  • indexing : index를 사용해 특정 요소를 리스트로부터 읽어들이는 것
  • slicing : 요소에 특정 부분을 따로 분리해 조작하는 것

---

3. 연결 리스트(Linked List)

데이터를 감싼 노드에 포인터를 연결한 공간적인 효율성 좋은 자료구조

동적 추가, 삭제 효율적 / 특정 위치의 노드 검색 비효율적(차례대로 접근)

출처 https://velog.io/@hyhy9501/5-1-Linked-List-%EC%97%B0%EA%B2%B0-%EB%A6%AC%EC%8A%A4

• 단순 연결 리스트 : Head에서 부터 Tail까지 다음 노드의 위치를 가리키면서 이동하는 구조(마지막 포인터는 NULL)
• 이중 연결 리스트 : 각 노드가 이전 노드와 다음 노드를 모두 참조하는 링크드 리스트
• 원형 연결 리스트 : Tail이 Head를 참조하는 링크드 리스트

---

4. 스택(Stack)

후입선출(LIFO : Last In, First Out) : 가장 나중에 들어온 데이터가 가장 먼저 나감(ex. 웹 페이지 뒤로가지, 문서작업 되돌리기 기능)

• 상단(stack top) : 스택에서 입출력이 이루어지는 부분
• 하단(stack bottom): 반대쪽 바닥 부분
• 요소(element): 스택에 저장되는 것
• 공백 스택(empty stack): 공백 상태의 스택
• 포화 스택(full stack): 포화 상태의 스택(풀스택)

 

스택의 연산

연산	기능
top()	스택 맨 위에 있는 데이터 값 반환
push()	스택에 데이터 삽입
pop()	스택에서 데이터 삭제하여 반환
isempty()	스택에 원소가 없으면 'True', 있으면 'False' 값 반환
isfull()	스택에 원소가 없으면 'False', 있으면 'True' 값 반환

---

5. 큐(Queue)

선입선출(FIFO : First In, First Out / LILO : Last In, Last Out) : 가장 먼저 들어온 데이터가 가장 먼저 나감 / 가장 나중에 들어온 데이터가 가장 나중에 나감(ex. 은행 대기표, 수강신청 등)

데이터의 삽입과 삭제가 각각 한쪽 끝에서만 일어나는 구조

데이터는 front에서 삭제, rear에서 삽입

• enqueue() - 큐에 끝(rear)에 항목을 추가
• dequeue() - 큐에 맨 앞(front)에 항목을 제거
• peek() - 큐에 맨 앞(front)에 있는 항목을 반환
• isfull() - 큐가 가득 찼는지 확인
• isempty() - 큐가 비어 있는지 확인

작업	Average	Worst
접근(Access)	Θ(n)	O(n)
검색(Search)	Θ(n)	O(n)
삽입(Insert)(enqueue)	Θ(1)	O(1)
삭제(Delete)(dequeue)	Θ(1)	O(1)

 

---

6. 우선순위 큐(Priority Queue)

먼저 들어오는 데이터가 아니라, 우선순위가 높은 데이터가 먼저 나가는 형태의 자료구조

힙(Heap)을 이용해 구현

힙이란?

힙(Heap)은 우선순위 큐를 위해 고안된 완전이진트리 형태의 자료구조

 

특징

• 완전이진트리의 형태로 이루어짐(완전이진트리랑 비슷하지만 노드간 대소관계 명확함)
• 부모노드와 서브트리간의 대소 관계가 성립함(반정렬 상태)
• 이진탐색트리(BST)와 달리 중복된 값이 허용됨    

종류

• 최대 힙(Max Heap)
  부모 노드의 키 값이 자식 노드보다 크거나 같은 완전이진트리
  📝 key(부모노드) ≥ key(자식노드)

최대 힙(Max Heap)

• 최소 힙(Min Heap)
  부모 노드의 키 값이 자식 노드보다 작거나 같은 완전이진트리
  📝 key(부모노드) ≤ key(자식노드)

최소 힙(Min Heap)

 

[출처]

https://suyeon96.tistory.com/31

https://wikidocs.net/178938

https://zu-techlog.tistory.com/31

---

7. 맵(Map)

Map은 Key와 Value 한 쌍으로 이루어진 자료형(딕셔너리와 동일)

• Key는 중복을 허용하지 않음(Unique)
• List와는 다르게 순서가 없고 key로 매핑해 value를 반환함
• 객체의 속성(Property)을 자주 변경해야 할 때 유리함

[출처]

https://dev.gmarket.com/68

---

8. 해시 테이블(Hash Table)

key, value로 데이터를 저장하는 자료구조

빠르게 데이터를 검색할 수 있는 자료구조

• 각각의 key값에 해시함수(hash function)를 적용해 배열에 고유한 index를 생성하고, 이것을 버킷(슬롯)에 저장
• 고유한 index를 통해 값을 저장하거나 검색함
• key값으로 데이터를 찾기 때문에 함수를 한 번만 수행하면 됨 O(1)

[출처]

https://preamtree.tistory.com/20

https://mangkyu.tistory.com/102