자료구조> 기본

 

 

 

배열

데이터를 나열한다.

각 데이터를 인덱스에 대응한다.

파이썬에선 리스트가 배열을 담당한다.

 

같은 종류를 효율적으로 관리

같은 종류를 순차적으로 저장

 

빠른 접근

추가/삭제가 쉽지 않다. 

고정/정적 => 미리 최대 길이 지정해야함

컴파일 이전에 크기 고정. 컴파일 이후에는 변경 불가

크기가 고정이라 삭제하면 빈자리.

 

랜덤 접근이 가능

인덱스를 사용하여 O(1) 시간 복잡도

 

스택에 저장 

컴파일할 때 메모리 할당 (Static Memory Allocation)

다차원 가능

 

 

클래스 객체가 아님

변수, 메소드 보유 X

 

리스트

배열의 인덱스를 버리고 빈틈없는 데이터 적재 (배열의 특징인 삭제하면 빈자리 생기는 것을 생각할 것)

메모리 관리 편리하고 메모리 재사용

인덱스가 아니라 순서. 리스트에서 인덱스는 순서를 의미한다.

포인터 사용해서 삽입 삭제 쉬움

불연속

동적. 크기가 안 정해져있음

포인터 공간 발생

 

랜덤 접근 불가능

Sequential access 처음부터 접근하고자 하는 곳까지 순회

따라서 시간복잡도 O(n)

 

힙 저장

런타임에 메모리 할당 (Dynamic Memory Allocation)

 

인퍼페이스/ 클래스 객체 멤버 메소드

 

 

 

자바의 List Collection

ArrayList/ LinkedList/ Vector 

ArrayList

배열처럼 인덱스로 관리. 순서가 인덱스.

배열과는 다르게 동적으로 크기 조절

데이터가 추가되는데 공간이 부족하면 50퍼센트가 증가한다. 

수정 삭제하면 전체가 이동

 

배열과 arrayList의 차이점

배열은 크기가 고정. arrayList는 동적

배열은 primitive type 과 object data 모두 담을 수 있다. arrayList는 object data만 담을 수 있다.

배열은 제네릭을 사용할 수 없지만 arrayList는 타입 안정성을 보장하는 제네릭을 사용할 수 있다.

배열은 length을 쓰고 arrayList는 size를 쓴다. 

Vector

Vector는 ArrayList와 동일한 내부 구조. Vector 객체를 생성하기 위해서는 저장 타입을 지정해야함.

Vector는 동기화된 메서드로 구성

동기화라서 ArrayList보다 추가, 삭제 과정이 느리다.

데이터 추가 시 공간이 부족하면 100퍼센트 증가

LinkedList

연결리스트

떨어진 곳에 있는 데이터를 화살표로 연결 관리하는 데이터 구조

파이썬은 리스트타입이 링크드리스트 기능 모두 지원

 

데이터 공간 할당 미리 안해도 됨

포인터 저장 공간 필요

데이터 접근 속도 느림

삽입 삭제 시 데이터 연결 재구성 작업 필요

 

 

ArrayList : 수정/ 삭제는 별로. 검색이나 마지막에 추가할 때는 좋음

LinkedList : 삽입 삭제에 좋음

Vector : 멀티 스레드에 사용

 

큐

First In First Out

멀티태스킹 프로세스 스케쥴링 방식

장단점보다는 프로세스 스케쥴링 방식을 함께 이해하자.

 

 

스택

Last In First Out

데이터 제한적 접근 구조

한 쪽 끝에서만 자료를 넣거나 뺀다.

스택 구조는 프로세스 실행 구조

컴퓨터 내부 프로세스 구조 함수 동작 방식

 

단순구조 구현쉬움

데이터 저장/읽기 빠름

=> 단순하고 빠른 성능

배열 구조를 활용해서 구현

 

데이터 최대 갯수 정해야 함

(파이썬은 재귀함수 1000번까지 호출 가능)

최대 갯수만큼 저장 공간 확보

 

 

해쉬테이블

Key 값과 Value 값을 저장하는 데이터 구조

Key 값을 통해 바로 뽑으니 속도 빠름

파이썬은 딕셔너리 타입

배열로 해쉬 테입르 사이즈만큼 생성 후 사용 따라서 저장공간 많이 필요

 

중복확인 쉬움

해시 주소가 중복되면 따로 처리 필요

 

검색이 많이 필요할 경우

저장 삭제 읽기가 빈번할 경우

캐쉬 구현 시 왜냐하면 중복확인이 쉬워서

해쉬 :

임의 값을 고정 길이로 변환

해쉬테이블 :

키 값 연산으로 직접 접근 가능한 데이터 구조

해싱함수 :

Key값을 산술 연산 통해서 데이터 위치를 찾는 함수

해쉬 값/ 해쉬 주소 :

Key 값을 해싱 함수로 연산하여 해쉬값을 알아내고

해쉬 테이블에서 해당 Key의 데이터 위치를 찾을 수 있음

슬롯:

데이터를 저장할 수 있는 공간

 

 

 

Chaining 기법

Linear Probling 기법