자료구조 : 배열, 연결리스트, 해시

1. 배열(Array)

같은 타입 데이터를 여러개 나열하는 선형 자료구조

연속적인 메모리 공간에 순차적으로 데이터 저장 -> 관리 편하다는 장점

선언시에 크기 지정, 인덱스 사용 가능

정적 메모리 항당 (컴파일 타임 -> 스택영역)

 

장점 : 순서유지, 인덱스 통해 특정 위치 요소 접근이 빠름

단점 : 크기 선언하면 그 뒤로 크기 제한, 배열 중간에 삽입/삭제 어려움, 지정한 크기 남으면 공간 낭비

 

 

2. Array List

배열 형태의 리스트, 동적+ (정적)

배열이 다 차면, 새로운 배열 만들어 기존 내용 복사

자바의 arrayList, c++의 vector

인덱스 접근 가능

 

장점 : 인덱스 통해 특정 위치 요소 접근이 빠름, 동적 크기 조정 가능

단점 : 기존 배열의 요소를 새 배열로 복사하는 비용, 배열 중간에 삽입/삭제 어려움, 배열 크기 지정 불가로 메모리 낭비

 

 

 

 

3. 연결리스트(Linked List)

불연속적인 곳에 존재하는 데이터를 화살표로 연결

삽입 삭제 많이 사용할 때, 크기 모를때 사용하기 좋음.

검색 할 때에는 처음부터 차례로 접근 해야하므로 비효율적

동적 메모리 할당(런타임 -> 힙)

 

장점 : 동적 크기 조정 가능, 배열 중간에 삽입/삭제 쉬움, 메모리 관리 유연(불연속적이라)

단점 : 검색 느림(순차적), 포인터 사용으로 메모리 추가 사용

 

 

1) 단순 연결 리스트

각 노드는 데이터와 다음 노드를 가리키는 포인터(링크)로 구성 / 리스트의 시작을 가리키는 포인터(head)만 존재하며, 각 노드는 오직 한 방향으로만 이동

 

 

 

2) 원형 연결 리스트

 

마지막 노드의 다음 포인터가 리스트의 첫 번째 노드를 가리킴 / 리스트의 처음과 끝이 연결되어 원형 형태를 이루며, head와 tail 포인터가 존재

 

+ 원형 이중 연결 리스트도 있음.

 

 

 

3) 이중 연결 리스트

각 노드는 데이터와 두 개의 포인터(하나는 다음 노드를 가리키고, 다른 하나는 이전 노드를 가리킴)로 구성 / 리스트의 시작을 가리키는 포인터(head)와 끝을 가리키는 포인터(tail)가 존재하며, 양방향으로 이동이 가능

 

 

 

 

4. 해시

키를 해시값으로 매핑, 이 해시값을 index로 삼아 데이터와 키를 함께 저장, key-value 형태

 

input으로 키를  해시함수에 넣어주면 output으로 해시가 나옴

* 해시함수 : 임의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수,

이 매핑 과정을 해싱이라곻 함.

* 해시 테이블 : 데이터가 저장되는 곳

 

장점 : 정확한 값 검색 빠름(key-value 매핑), 삽입/삭제 빠름 O(1)

단점 : 해시 충돌 가능, 순서 있는 배열 비추, 해시함수 의존도 높음(함수가 복잡하면 시간 증가)

* 해시 충돌 : 키 값 다른데 해시값이 동일한 현상

 

- 해시충돌 해결

1) 체이닝(Chaining) 기법

2) 개방 주소법(Open Addressing)