자료구조란 뭘까
자료구조는 Data Structure로 데이터 구조 더 자세히 설명하면 '일련의 일정 타입들의 데이터 모임 또는 관계를 나타낸 구성체'라고 말할 수 있다.
자료구조와알고리즘은 서로 뗄 수 없는상호 의존적인 관계- 왜 상호 의존적이냐? 알고리즘 문제를 풀기 위해 문제를 해석한 다음 보통 자료구조를 선택
- 자료구조를 선택하면 해당 자료구조에 맞는 알고리즘을 선택하는데 보다 더
효율적인 알고리즘을 선택할 수 있다는 장점 - 예를 들어 순서가 있는
데이터 삽입 (insert/add),삭제 (remove/delete)가빈번하게 발생하면LinkedList, 아닐 경우ArrayList를 쓰듯이 각자료구조별로장단점이 존재. 따라서알고리즘 선택에 있어 매우중요한 역할을 담당 - 이러한 자료구조 이해를 돕기 위해 이번에 자바의 대표적인 자료구조인
Collection을 배워보는 시간
자료구조 분류
선형 자료구조 (Linear Data Structure)
= 데이터가 일렬로 연결된 형태. 흔히 쓰는 int[] 배열과 같다.
- 대표적으로
리스트(List),큐(Queue),덱(Deque)이 있음.
비선형 자료구조 (Nonlinear Data Structure)
= 데이터가 일렬로 나열된 것이 아닌, 각 요소가 여러 개의 요소와 연결 된 형태. 쉽게 말해서 거미줄 같다고 보면 된다.
- 대표적으로
그래프(Graph)와트리(Tree)
집합 (Set)
= 자료구조 중 위 두 가지 분류에 해당되지 않는 자료구조이다. 데이터가 연결된 형식이 아니다.
Java Collections FrameWork
기본 구조라고 한다면 딱 떠올려야 할 것이 바로 Interface(인터페이스)이다.
인터페이스 자체가 기본 뼈대(추상 구조)만 있음. 이렇듯 실제로 자바에서 제공하는 Collection은 크게 3가지 구조로 나뉨.
List(리스트), Queue(큐), Set(집합) -> 형태에 따른 자료구조라고 보면 된다
- 점선은 구현 관계고 실선은 확장 관계다.
인터페이스 (하늘색 박스)
인터페이스는 메서드의 구현 없이 메서드의 형태만 정의한 것임. 인터페이스는 이를 구현하는 클래스가 반드시 해당 메서드를 구현하도록 강제한다.
클래스 (초록색 박스)
실제로 구현된 클래스임. ArrayList, LinkedList, HashSet 등은 해당 인터페이스를 구현하고, 구체적인 동작을 정의한 클래스들입니다. 이들은 인터페이스가 정의한 메서드들을 실제로 구현한다.
List
List Interface 는 대표적인 선형 구조 = 주로 순서가 있는 데이터를 목록으로 이용할 수 있음
List를 통해 구현된 클래스들은 동적 크기를 갖으며 배열처럼 사용할 수 있음.
(일반 배열에서 int[] array = new int[10] -> 10개의 공간 외에는 IndexOutofBoundsException 에러 발생 )
List를 통해 구현된 클래스 => 배열의 기능 + 동적 크기
List Interface를 구현하는 클래스
- ArrayList
- LinkedList
- Vector (+ Vecto를 상속 받은 Stack)
List Interface에 선언된 대표적인 메소드
ArrayList
Object[] 배열을 사용하면서 내부 구현을 통해 동적으로 관리- 최상인 타입인 Object 타입으로 배열을 생성하여 사용하기 때문에 요소 접근에서는
탁원한 성능 - 중간의 요소 삽입, 삭제가 일어나는 경우 그 뒤의 요소들은 한 칸씩 밀어야 하거나 당겨야하기 때문에
삽입,삭제에는비효율적인 모습을 보임
LinkedList
데이터와 주소로 이루어진 클래스를 만들어 서로 연결하는 방식- 데이터와 주소로 이루어진 클래스를
Node(노드)라고 함 - 각 노드는 이전의 노드와 다음 노드를 연결하는 방식. -> 즉 객체끼리 연결한 방식
- 요소를 검색해야 할 경우 처음 노드부터 찾으려는 노드가 나올 때 까지 연결된 노드들을 전부 방문 -> 성능 저하
- 해당 노드를 삭제, 삽입해야 할 경우 해당 노드의 링크를 끊거나 연결만 해주면 되기 때문에 삽입, 삭제 ->
성능 상승
Stack
- 흔히 생각하는 것과 같이 쌓아 올리는 것
- LIFO (Last In First Out) = 후입선출
- 뒤로가기 생각하면 됨 = 우리가 새로운 페이지 방문하는것: Stack 쌓아 올림, 뒤로가면 하나씩 Stack 없앰
