배열(array)
-
같은 자료형을 가진 변수를 하나로 나타낸것
-
연속된 메모리 공간으로 이루어져있는 것.'
-
정적 표현
-
인덱스를 이용하여 표현
-
지역성을 가지고있다.
배열의 장단점
*장점
- 인덱스를 통한 검색 , 연속적이므로 메모리 관리가 편하다.
*단점
- 한데이터를 삭제하더라도 배열은 연속해야하므로 공간이 남는다(메모리낭비)
- 정적이므로 배열의 크기를 컴파일 이전에 정해주어야 한다.
- 컴파일 이후 배열의 크기를 변동할 수 없다.
리스트(list)
- 순서가 있는 데이터의 집합
- 불연속적으로 메모리공간을 차지.
- 동적표현
- 인덱스가 없음
- 포인터를 통한 접근
리스트의 장단점
*장점
- 포인터를 통하여 다음 인덱스르 가르키고있어서 삽입삭제가 용이
- 동적이므로 크기가 정해져있지 않다.
- 메모리 재사용 편리
*단점
- 검색성능이 좋지 않다.
- 포인터를 통해 다음 데이터를 가르키므로 메모리낭비
스택(stack)
자료의 입력과 출력을 한 곳(방향)으로 제한한 자료구조.
LIFO(Last In First Out)구조 push(), pop()
함수의 콜스택에 쓰이고 문자열을 역순으로 출력할 때, 연산자 후위표기법등에 쓰인다.
큐(queue)
자료의 입력과 출력을 한 쪽 끝(front, rear)으로 제한한 자료구조.
FIFO(First In First Out)구조 put(), get()
컴퓨터 버퍼에서 주로 사용, 마구 입력이 되었으나 처리를 하지 못할 때, 버퍼(큐)를 만들어 대기 시킨다.
일반적인 큐의 단점 : 큐에 빈 메모리가 남아 있어도 꽉 차있는것으로 판단할 수 있음 rear가 배열의 끝에 도달했을 경우.
=> 개선된 원형 큐가 나옴.
원형 큐의 단점 : 메모리 공간은 잘 활용하나 배열로 구현되어 있기 때문에 큐의 크기가 제한되는 단점이 존재
=> 링크드리스트로 큐가 나옴.
링크드 리스트로 구현한 큐는 큐의 크기가 제한이 없고 삽입, 삭제가 편리하다.
덱(deque)
자료의 입력과 출력을 양 쪽 끝에서 가능하게 하는 자료구조.
스크롤(scroll) : 입력이 한쪽 끝으로만 가능하도록 제한한 덱
셸프(shelf) : 출력이 한쪽 끝으로만 가능하도록 제한한 덱
해시테이블
키(Key)를 이용하여 값(Value)를 저장하는 자료구조이다.(예: python의 dict)
키(Key)를 특정 해시 함수(Hash Function)를 통해 해싱한 후 나온 결과(정수)를 배열의 인덱스로 사용하여 값(Value)를 찾는다. 검색 성능은 해시 함수의 성능과 해시 테이블의 크기에 좌우된다.
{ "연필" : 200, "볼펜" : 300, "샤프" : 3000, "필통" : 15000 }
의 데이터가 있으면 키(Keys)를 특정 해시 함수(Hash Function)을 사용하여 다음과 같은 해시 테이블의 인덱스 형태로 만든 후 값(Values)을 저장한다.
장점과 단점
해싱된 키(Hash Key)를 가지고 배열의 인덱스로 사용하기 때문에 삽입, 삭제, 검색이 매우 빠르다.
해시 함수(Hash Function)를 사용하는데 추가적인 연산이 필요하다.
적은 데이터 저장시 구현 방식에 따라 연결리스트(Linked List)를 사용하는 경우 오버 헤드의 부담이 생기고, 캐시 효율이 떨어진다.
해시 테이블(Hash Table)의 크기가 유한적이고 해시 함수(Hash Function)의 특성상 해시 충돌(Hash Collision)이 발생할 수 밖에 없다.
충돌이 없거나 적으면 O(1)의 상수 시간에 가까워지고, 충돌이 발생하면 할수록 성능은 점점 O(n)에 가까워진다.
