선형 : 배열, 리스트, 스택, 큐
비선형 : 그래프, 트리, 힙
리스트
데이터를 순서대로 나열한 자료구조
- 선형 리스트 : 데이터가 배열처럼 연속하는 메모리 공간에 저장된 자료구조
- 연결 리스트 : 데이터가 메모리 공간에 연속적으로 저장되어 있지않더라도 노드포인터를 이용해 접근할 수 있는 연결된 자료구조
연결 리스트
- 메모리 동적 할당을 기반으로 한다.
- 각 데이터들이 연속적으로 저장되지 않지만 데이터 안에 다음 데이터에 대한 정보(노드 포인터)를 갖는 구조
데이터 조회
- 배열 - 시간복잡도 O(1)
인덱스로 접근 하기 때문에 시간복잡도 - O(1) - 리스트 - 시간 복잡도 O(N)
Head를 통해 들어와 첫 노드부터 순차적 접근
모든 데이터를 탐색해야 함 - 시간 복잡도 O(N)
👉 조회 기준으로 배열이 리스트보다 빠르다
데이터 삽입
- 배열 - 시간 복잡도 O(N)
삽입 후 나머지 데이터들 값 이동
값을 맨 앞에 이동시 모든 데이터들의 값을 이용해야 하기 때문에 시간이 오래걸림 - 리스트 - 시간복잡도 O(1)
삽입 위치 전 후 데이터의 연결만 변경
👉 삽입 기준으로 리스트가 배열보다 빠르다
데이터 삭제
- 배열 - 시간 복잡도 O(N)
삭제 후 나머지 데이터 값 이동 - 리스트 - 시간복잡도 O(1)
삭제 위치 이전 데이터의 연결만 변경
👉 삭제 기준으로 리스트가 배열보다 빠르다
이중 연결 리스트
- 각 노드마다 이전 노드와 다음 노드 포인터가 존재
- 노드를 양방향으로 탐색이 가능
ex) LinkedList, Deque
배열과 리스트
배열과 리스트의 특징
1) 배열
- 인덱스 이용해서 바로 접근 가능 해서 조회를 가능 하지만 새로운 값 삭제, 삽입 시 비효율적
- 선언할 때 크기가 고정되기 때문에 크기 변경시 재할당 필요
- 구조가 간단하여 쉽게 사용 가능
2) 리스트
- 포인터를 이용해서 인덱스가 없기에 값에 접근할 때 head 포인터부터 순차적으로 접근해야 해서 속도가 느리다
- 포인터로 연결되어 있어 데이터 삽입, 삭제 연산이 빠름
- 크기가 가변적이기 때문에 변하기 쉬운 데이터 다룰때 사용
- 포인터를 저장하기 때문에 배열보다 구조가 복잡하고 메모리가 필요
- 기본 배열
- 사이즈 고정
- Primitive/Object 타입 모두 가능
- java.util.ArrayList
- 사이즈 가변적
- 배열 기반
- Object 타입만 가능
- 시간 복잡도 : 배열 - 조회 O(1), 삽입/삭제 O(N)
Type - Object
int Integer, boolean ->Boolean
- java.util.LinkedList
- 사이즈 가변적
- 이중 연결 리스트 기반
- Object 타입만 가능
상황에 맞게 사용하기
변수 사이즈 변경 X - 배열 사용
사이즈 변경 O - 조회 - ArrayList
- 삽입/삭제 - LinkedList
스택
- 스택은 데이터를 쌓아 올린 형태의 자료구조
- 후입선출 (LIFO; Last In First Out)
- push() : 데이터 삽입, pop() : 데이터 빼기(?)
- 스택의 꼭대기 부분 : peek
큐
- 일렬로 늘어선 데이터를 일시적으로 쌓아두는 자료구조
- 선입선출 FIFO
- 인큐(en-queue) : 큐에 데이터를 넣는 작업
- 디큐(de-queue) : 큐의 데이터를 꺼내는 작업
- Queue 메소드
offer(), add() : 큐에 데이터를 인큐(추가)
remove(), poll() : 큐에서 데이터 디큐(삭제)
peek() : 맨앞 데이터 반환
isEmpty() : 큐가 비어있으면 true, 그렇지 않으면 false 반환
toString() : 큐에 저장된 값을 문자열로 변환
❗ arraylist 형식으로 선언 시 에러 발생 - 객체화 불가능
👉 Queue는 인터페이스 객체이기 때문에 객체 생성 불가
ArrayDeque, LinkedList 로 생성
Queue<Integer> que_array = new ArrayDeque<>();
Queue<Integer> que_list = new LinkedList<>();큐 생성시 ArrayDeque 사용 추천
스택 - DFS 구현
큐 - BFS 구현
Deque (이중 연결 리스트; Double-Ended Queue)
- 덱(Deque)은 큐의 앞부분(
front)와 뒷부분(rear)에서 모두 삽입 삭제 가능 - 이중 연결리스트로 구현
- java.util.Deque 인터페이스로 구현 가능
- 변수 : Head(맨 앞부분), Tail(맨 뒷부분)
add_front() : Head 추가
get_front() : Head 조회
delete_front() : Head 삭제
add_rear() : Tail 추가
get_rear() : Tail 조회
delete_rear() : Tail 삭제
Java 선형 자료구조
( 추후 추가 )
Just Do IT ------- 🏃♀️