선형 자료 구조 _ 연접 리스트(배열)

자료구조: 데이터 집합체를 어떻게 구조화 시키고 관리할 것 인가?

 

- 선형 자료 구조

1) 연접리스트 (배열) : 메모리적으로 연결

2) 연결리스트 (단일, 이중, 환영 리스트): 논리적으로 연결

-----------------------------------------------------------------------------------------------------------------

나머지 자료구조들은 배열이나 연결 리스트를 응용해서 구현!

-> 스택(Stack), 큐(Queue), 덱(Deque)

 

- 비선형 자료 구조

1) 트리

2) 그래프

3) 해쉬 테이블

 

연접 리스트(배열): 물리적 선형 자료구조

데이터 저장 관리를 배열이라는 자료구조로 하겠다.

- Insert(저장), Select(검색), Update(수정), Delete(삭제)

 

배열 자료구조 성질!

- 항상 0번째 인덱스부터 순차적으로 저장된 형태를 유지하겠다.

프로그램의 구조

배열 자료구조

1단계 : 클래스 정의, 맴버필드 구성

클래스 명 : BitArray

1) 저장소 : 배열    ==> - base : Object[]

2) max : 최대 크기  ==> - max : int

3) size : 저장개수, 저장위치 ==> - size: int

2단계 : 생성자 정의[맴버 필드의 초기화]

1) max 값 초기화 [매개변수 전달]

2) size <- 0;

3) 배열을 max값 크기에 맞추어 동적 할당

 

3단계: insert (저장 기능)

public void insert(Object obj){ .... } 

 

1) isOverflow 메소드 생성 (리턴값: boolean) 

- 저장 공간이 다 찬 상태인가 확인

2) base[size] = obj;

3) size++;

 

3단계: delete (삭제 기능)

public void delete(int idx){ .... }

 

1) isUseIdx 메소드 생성 (매개변수: int idx, 리턴값: boolean)

- 유효한 인덱스인가? (0 ~ size-1)

2) 반복문을 활용해서 이동

for(int i = idx; i < size-1; i++){

   base[size] = size+1; 

}

3) 사이즈 감소

 

4단계 : select (검색 기능)

1) 순차 검색 : 시작 -> 끝 순차적으로 -> 오늘 구현 내용

for(int i = 0; i < size; i++){ .... }

 

2) 이분법적 검색 : 정렬을 전제로 한다.

- 순회

- 구간[시작점, 끝점]

 

 

※ 싱글톤 패턴

 

객체를 하나만 생성할 수 있는 클래스를 만들고 싶다.

1. 생성자가 외부로 노출되면 안됨.

2. 해당 클래스에서 내부적으로 객체를 만든다

멤버 필드로 객체를 선언하고 생성(static)

3. 객체를 외부에 노출시킬 static 메소드 제공

 

[싱글톤 템플릿]

 

// 싱글톤 패턴 코드
// =====================================================================
private Manager() {
   arr = new BitArray(inputMax());
}

private static Manager Singleton = new Manager();

public static Manager getInstance() {
   return Singleton;
}

// 싱글톤 패턴 코드
// =====================================================================

 

 

 

 

 

 

0209_1일차관리프로그램_Ver2.0.zip

0.01MB

Java자료구조.pptx

0.10MB