[CS 스터디 : Java] (1) Array, ArrayList, LinkedList

 

 

1️⃣ Array, 배열

: 자료형의 집합

 

→ 선언 방식

 

→ 배열의 특징

  (1) 배열의 길이(크기)는 고정

  (2) 반복문과 인덱스를 통해 배열의 값 접근

  (3) [배열이름.length] 를 사용해 배열의 길이 접근

 

---

 

 

 

 

 

2️⃣ ArrayList

: 배열과 유사한 자료형의 집합

: List 자료형(인터페이스) 중 하나

 

→ 선언 방식

-- java.util.ArrayList 패키지를 import 해서 사용

-- ArrayList<Generic 명> 리스트이름 = new ArrayList<Generic명>();

 

 

 

→ ArrayList의 특징

  (1) 배열의 길이가 동적으로 변함 > 원하는 만큼의 값을 담을 수 있음 > 자동으로 크기가 늘어남

  (2) 다양한 메서드를 제공 > CRUD 구현 가능

메서드 기능	메서드 명	반환 타입
원소 추가(C)	add(E e)	boolean
	add(int index, E element)	void
원소 접근(R)	get(int index)	E
배열 확인	isEmpty()	boolean
배열 삭제(D)	remove(int index)	E
	remove(Object o)	boolean
배열 수정(U)	set(int index, E element)	E
배열 크기 확인	size()	int
배열 원소 확인	contains(Object o)	boolean
ArrayList → Array	toArray()	Object[]
	toArray(T[] a)	<T> T[]

 

(3) isEmpty, size, get, set, iterator, listIterator 은 상수 시간 복잡도(O(1))를 가짐

(4) add는 O(n) 의 복잡도를 가짐 > 특정 위치에 추가할 시에 리스트의 원소들을 재배열해야 하기 때문

(5) 다른 메서드들은 선형 시간 복잡도를 가짐 

 

✅ 배열 → ArrayList 변환

  -- java.util.Arrays 패키지의 asList 메서드 사용

  -- Arrays.asList(배열) : List<T> 로 반환

---

 

 

 

 

 

 

3️⃣ LinkedList, 연결리스트

: 데이터가 노드로 연결되어 있는 리스트의 형태

: List 자료형(인터페이스) 중 하나

: 노드는 데이터와 포인터(next, prev)를 가지고 있음 

: 자바 java.util.LinkedList 패키지에는 양방향 연결 리스트로 구현되어 있음

 

자바 노드 구조

 

노드가 연결된 연결리스트의 형태

 

→ 선언 방식

-- java.util.LinkedList 패키지 임포트해서 사용

 

 

→ LinkedList 특징

  (1) 데이터를 추가, 삭제에 용이 > 포인터만 주소값에 연결해주면 되기 때문에

  (2) 특정 데이터 접근에는 ArrayList 보다 떨어진 성능을 보임 > 사실상, 처음 or 마지막부터 포인터를 따라 주소값을 찾아가야 하기 때문

  (3) 자바에서는 ArrayList 메서드 모두 제공

  (4) LinkedList에서만 제공 > 리스트 앞 뒤에 삽입 & 삭제하는 메서드가 많음 + 스택 메서드도 존재

메서드 기능	메서드 명	반환 타입
맨 앞에 원소 추가 (C)	addFirst(E e)	void
	offerFirst(E e)	boolean
	push(E e)	void (리스트를 스택 형태라고 생각)
맨 뒤에 원소 추가 (C)	addLast(E e)	void
	offerLast(E e)	boolean
첫 번째 원소(head) 접근 (R)	getFirst()	E (배열이 null일 경우, runtime error)
	peekFirst()	E (배열이 null일 경우, null 반환)
	peek()	E (배열이 null일 경우, null 반환)
마지막 원소 접근 (R)	getLast()	E (배열이 null일 경우, runtime error)
	peekLast()	E (배열이 null일 경우, null 반환)
첫 번째 원소 삭제 (D)	remove()	E (삭제된 원소 반환, 배열이 null일 경우→ runtime error)
	removeFirst()	E (삭제된 원소 반환, 배열이 null일 경우→ runtime error)
	pop()	E (리스트를 스택 형태라고 생각)
	poll()	E (삭제된 원소 반환, 배열이 null일 경우→ null 반환)
	pollFirst()	E (삭제된 원소 반환, 배열이 null일 경우→ null 반환)
마지막 원소 삭제 (D)	removeLast()	E (삭제된 원소 반환, 배열이 null일 경우→ runtime error)
	pollLast()	E (삭제된 원소 반환, 배열이 null일 경우→ null 반환)

  

---

 

 

 

 

4️⃣ Array & ArrayList & LinkedList

	Array	ArrayList	LinkedList
크기	정적인 크기 (크기 지정 O)	동적인 크기 (크기 지정 O / X)	동적인 크기 (크기 지정 X)
특정 데이터 접근	index 사용 & 빠름	get 사용 & 빠름	get 사용 & 느림
데이터 삽입, 삭제	삽입 시 크기 제한 존재 특정 인덱스에 삽입/삭제 시에 배열 전체를 변경 해야 함	특정 인덱스에 삽입/삭제 시에 진행되는 연산이 느림	특정 인덱스에 삽입/삭제 시에 주소값만 수정하여 연결하기 때문에 빠름
패키지	Arrays	Collections

 

 

 

 

 

 

🧲 출처

LinkedList 그림 : https://www.programiz.com/java-programming/linkedlist

Java LinkedList (With Examples)