자료구조

stack

- push(), pop(), peek() 

- LIFO : last in first out

- overflow : 할당된 stack 안에 함수가 너무 많이 쌓여서 넘치는 경우 에러

ex) 재귀함수 break 없이 무한대로 호출, 복잡한 함수 실행 시 발생 가능

 

Queue

- FIFO : first in first out

- ex) 예약시스템 : 먼저 클릭한 사람부터 처리

 

LinkedList 

- 메모리에서 연속해서 존재하지 않음

=> 각각 다른 위치에 존재하며 포인터(링크)를 가지고 있어 다음 노드의 위치를 알 수 있음

- 단순 연결 리스트 : 한방향으로만 감

- 이중 연결 리스트 : 양방향으로 검색가능 ( 이전 노드의 위치 정보, 다음 노드의 위치 정보 둘 다 가지고 있음 )

- 삽입 삭제가 용이 ( 가르키고 있는 링크의 주소만 바꿔주면 됨 )

기준	배열	연결 리스트
메모리 할당	고정된 크기, 연속된 메모리 할당	동적 할당, 각 노드가 개별적으로 할당
삽입 / 삭제	느림 (배열의 크기 변경 또는 요소 이동 필요)	빠름 (포인터 조정만 필요)
접근 방식	인덱스를 통한 직접 접근 arr[1] (탐색에 용이)	순차접근 linkedList[n] n:노드 수 (어디를 가리키고 있는 지 일일이 확인, 노드 수가 많아질수록 부담)
메모리 사용	낮음 (추가적인 포인터 필드 없음)	높음 (각 노드가 포인터 정보를 추가로 저장)
사용 용이성	간단한 구현 및 사용	포인터 사용으로 인한 복잡한 구현

 

Hash

- 무한한 데이터를 유한한 테이블에 넣어줌 => 서로 다른 데이터가 같은 인덱스를 부여 받을 경우 충돌발생하는 단점

- Map의 구조 ( key : value )

- 충돌 해결

 1. 체이닝

서로 다른 데이터가 같은 인덱스를 부여 받아 충돌이 발생할 경우 LinkedList로 연결 (같은 인덱스에 데이터1-데이터2-데이터3)

2. open addressing

충돌 발생 시 그 다음 비어있는 공간(주소지)으로 들어가게 됨

-> 찾을 경우 : 처음 배정받은 인덱스로 가서 그 인덱스 기준으로 내려가며 탐색

* 충돌방지

- 해시 테이블 사이즈 적절하게 설정

- 인덱스가 너무 겹치지 않도록 Hash 함수를 잘 설정