[자료구조와 알고리즘] 자바 자료구조, 선형구조 - 배열 (2023.04.06)

🎈 자료구조의 종류

단순구조

: 2진수, 정수 / 실수, 문자 / 문자열

선형구조

: 배열, 연결리스트, 덱, 스택, 큐

비선형구조

: 트리, 그래프

파일구조

: 순차 파일, 섹션 파일, 직접 파일

 

🎈 선형구조와 비선형구조

📖 선형구조 

자료를 구성하는 데이터를 순차적으로 나열시킨 형태

ex. 리스트(배열), 연결리스트, 덱, 스택, 큐

 

연결리스트
리스트와 달리 연속된 메모리 공간을 가지는 것은 아니지만, 데이터들의 앞/뒤로 다음에 나와야하는 데이터가 메모리상에 어디에 존재하는지 주소값을 가지고 있음. 자신과 연결된 데이터의 주소 데이터를 가지고 다음 값을 찾음

덱/스택/큐 
데이터 처리 방식에 따라 분류. 스택은 먼저 들어온 데이터가 제일 마지막으로 나가는 구조인 반면, 큐는 제일 먼저 들어온 데이터가 제일 먼저 나가는 구조

 

📖 비선형구조

하나의 자료 안에 여러개의 자료가 존재할 수 있는 것

ex 1. 트리

폴더 구조에서 많이 쓰이며, 루트로부터 시작해 가지로 뻗어나가는 구조.

하나의 자료 안에 또다른 자료가 존재할 수 있고, 그 자료 안에 또 다른 자료 존재할 수 있음.

ex 2. 그래프

가지만 뻗어 나갈 수 있는 트리와 달리 순환이 가능함

 

🎈 리스트(배열)

연속적인 메모리 공간

들어갈 수 있는 데이터는 같은 형태만 가능 

단점

- 크기 지정이 필수 → 크기 변경이 불가함 / 고정 크기 이상의 객체를 관리할 수 없다.

- 배열의 중간에 데이터를 삽입 혹은 삭제하려면 일일이 기존 데이터를 옮겨줘야 함. 

 

🎈 컬렉션(Collection)

위와 같은 배열의 단점을 해결할 수 있는 방법

요소(element)라고 불리는 가변 개수의 객체들의 모음 → 요소의 개수를 변동할 수 있음

요소의 개수에 따라 자동 크기 조절

삽입 삭제에 따른 요소의 자료 이동 자동 관리

 

📖 컬렉션의 종류 : 리스트(list) & 셋(set)

리스트(List) → 순서가 있음 (연결리스트, 스택, 벡터, ArrayList 등) 

셋(Set) - 순서가 없음 (HashSet, SortedSet)

 

 📖 ArrayList<E>

배열을 좀 더 쉽게 다룰 수 있도록 컬렉션에서 제공

가변개수(개수를 변경할 수 있음)

가변 크기 배열을 구현한 클래스

 

⚙️ ArrayList<E> 제네릭 (E : element , 요소의 형태)

특징

1. 같은 형태만 들어갈 수 있음

배열 : int[] / String[] / char[] →  ArrayList<E> : ArrayList<integer>, ArrayList<String>

* ArrayList<>도 가능

→ 어떤 데이터든지 저장 가능 

→ 프로그램이 시작되면 그 때 ArrayList 안에 들어가는 데이터의 형태를 확인 

    실행을 했을 때 형태 지정

     만약, 무조건 ArrayList에는 정수형만 넣을거야, 다른 형태가 들어가면 오류가 나게 할거면 ArrayList<integer>로 작성

** 배열은 형태가 이미 정의가 되어 있음 → 컴파일 전에 데이터의 형태를 확인하고 오류 확인 가능

2. 연속적인 공간을 할당하고 선언시 크기 지정 가능 

  - 리스트의 맨 뒤에 객체 추가 (공간이 모자라면 자동 늘림)

  - 리스트의 중간에 객체 삽입 → 삽입된 뒤의 객체는 뒤로 하나씩 이동

  - 임의의 위치에 있는 객체 삭제 가능 → 객체 삭제 후 자리 이동. 

    (ArrayList에 빈값은 넣을 수 있으나 아무것도 넣지 않는 것은 불가능하기 때문) 

 - 공간을 늘릴 시 기존 메모리 뒤의 공간을 늘리는 것이 아님. 다른 더 넓은 공간을 찾아서 원래 있던 데이터는 자동 복사해서 옮김. → 크기를 넉넉하게 미리 잡아서 복사의 수를 줄이도록...

 

ArrayList<String> al = new ArrayList<String>(7)
ArrayList<자료형> 변수명 = new <요소의형태>(초기크기)

- 초기 크기는 생략시 기본값은 10
- new ArrayList : 힙 영역에 저장 → 코드 상 바로 접근 불가능
- ArrayList<String> al : 참조값(레퍼런스 변수)를 스택 영역에 저장

 

⚙️ ArrayList의 다양한 메서드

 

 

 

int 자료형을 쓰고 싶으면 Integer 클래스(레퍼런스 타입)를 사용해야 함. 

boolean, char 마찬가지로 기본타입이 아닌 레퍼런스 타입으로 넣어줘야 함. 

 

 

MusicPlayList 만들기

point 1) menu 변수 하나만 사용하여 코드 작성 가능

point 2) 플레이리스트가 1번 선택했을 때, 2번 선택했을 때 중복 출력 → 메서드를 만들어서 사용