[DataStructure] Array & ArrayList & LinkedList (JAVA) 정리

Array (배열)

배열이란 같은 데이터 타입의 변수들로 이루어진 자료구조로, 자바에서 기본적으로 지원하는 자료 구조이다.

배열을 구성하는 각각의 값은 요수 혹은 원소(element)라고 부릅니다. 배열에서의 위치를 가리키는 숫자는 인덱스(Index)라고 부릅니다.

대부분의 언어에서 배열의 인데스는 0부터 시작하며, 자바에서도 0부터 시작한다.

대부분의 언어에서 배열의 인덱스는 0부터 시작하며, 자바에서도 0부터 시작한다. 참고로 파이썬의 경우 배열과 비슷한 list에서 리스트 맨 끝의 원소를 가리키는 인데스 -1도 존재하는데, Java에서는 배열의 인덱스는 0을 포함한 양의 정수만 가질 수 있다.

배열은 참조 객체이므로 배열을 가리키는 참조 변수는 스택영역에 할당되며, 이 참조 변수가 가리키고 있는 주소값은 실제 힙 영역에서 생성되는 배열의 주소값이다.

 

Array(배열)의 특징

• 여러 데이터를 하나의 이름으로 그룹핑해서 관리 하기 위한 자료구조. index와 값의 쌍으로 구성
• index는 값에 대한 유일무이한 식별자
• 논리적 저장 순서와 물리적 저장 순서가 일치 => index로 해당 원소에 접근할 수 있다. (O(1))
• random access(비순차적 접근)가 가능
• 연속된 메모리의 공간 으로 이루어져 있다
• 배열은 정의와 동시에 길이를 지정 하며 길이를 바꿀 수 없다.

장점

• 인덱스를 통한 검색이 용이함.
• 연속적이므로 메모리 관리가 편하다.
• 인덱스 연산자를 사용할 수 있기 때문에, 특정 위치에 있는 원소에 대한 접근 및 수정의 시간복잡도는 O(1)이다.

단점

• 배열의 크기가 고정적이라 더 많은 데이터를 저장하기 위해서 더욱 큰 배열을 만들고 이전 배열의 데이터를 새로 만든 배열로 복사해야하는 불편함이 있습니다. 결국 새로운 배열로 데이터를 이동시키는 데에는 O(n)만큼의 시간복잡도가 소요됨으로 다뤄야 할 데이터의 개수가 가변적이고 예상하기 어렵다면 사용하기가 어렵다.
• 배열의 크기가 고정되어 있기때문에 어떤 엘리먼트를 삭제하게 된다면, 삭제된 상태를 빈 공간으로 남겨두어야 한다 -> 메모리 낭비가 발생한다. 또한 배열의 중간의 위치한 인덱스의 엘리먼트를 삭제하려면 삭제하고자하는 위치의 인덱스 뒤에 있는 원소부터 배열의 맨 끝에 있는 원소까지 앞으로 한 칸씩 직접 재할당해줘야한다. 그렇기에 시간복잡도가 O(n)만큼 소요된다.
• 배열의 크기가 고정되어 있기때문에 배열중간에 원소를 삽입해야하는 경우, 삭제의 경우와 동일하게 삽입하고자 하는 위치의 인덱스 두에 있는 원소부터 배열의 맨 끝에 있는 원소까지 뒤로 한 칸씩 직접 재할당해줘야 한다. 뒤로 한칸씩 민 원소의 갯수가 K라고 할때 이 작업은 K만큼의 연산 시간이 소요되며, K는 최대 N-1까지 될수 있음으로, 시간복잡도는 O(n)만큼 소요된다.

Java의 배열 초기화

배열은 생성과 동시에 자동초기화 된다. 자동초기화란 자동으로 초기값을 주는 것.

• 타입별 자동 초기화 값
• 정수(int, long) : 0
• 실수(double, float) : 0.0
• 논리값(boolean) : false
• 문자(char) : 공백 ( 공백문자 \u0000)
• Object(String 포함) : null

public class Main {


	public static void main(String[] args) {

		int[] arr = { 1, 2, 3, 4 };

	}

}

시간복잡도

1) 원소 찾기 : O(1)
2) 원소 추가/삭제 : O(N)
4) List의 크기 구하기 : O(N)

List (리스트)

리스트는 순서가 있는 엘리먼트의 모임으로 배열과는 다르게 빈 엘리먼트는 절대 허용하지 않는다.

리스트는 배열이 가지고 있는 인덱스라는 장점을 버리는 대신에 빈틈없는 데이터의 적재라는 장점을 취했다.

리스트에서 인덱스는 몇 번째 데이터인가 정도(순서)의 의미를 가진다.

자바에서 다수의 데이터를 쉽고 효과적으로 처리할 수 있는 표준화된 방법을 제공하는 클랫의 집합을 컬렉션 프레임워크(collection framework)라고 한다. 이러한 컬렉션 프레임워크는 자바의 인터페이스를 사용하여 구현되며, 리스트(List)는 컬렉션 프레임워크의 주요 인터페이스 중 하나입니다.

 

List의 특징

• 리스트 인페이스는 순서가 있는 데이터의 집합으로, 데이터의 중복을 허용한다.
• 리스트는 배열이 가지고 있는 인덱스라는 장점을 버리고 대신 비틈없는 데이터의 적재라는 장점을 취했다.
• 리스트에서 인덱스는 몇 번째 데이터인가 정도(순서)의 의미를 가진다.(배열 - Array에서의 인덱스는 값에 대한 유일무이한 식별자)
• 배열과 다른 점은 저장 공간의 크기가 고정되지 않고 가변적이라는 점, 중간에 빈 공간을 허용하지 않다는 점입니다.

장점

• 포인터를 통하여 다음 데이터의 위치를 가르키고 있어 삽입,삭제의 용이
• 동적이므로 크기가 정해져 있지 않다.
• 메모리의 재사용이 편리하다.
• 불연속적이므로 메모리 관리의 편리하다.

단점

• 검색 성능이 좋지 않다.
• 포인터를 통해 다음 데이터를 가르키므로 추가적인 메모리의 공간이 발생한다.

Java List Collection

List는 Collection 인터페이스를 확장한 자료형으로 동일한 데이터의 중복 입력이 가능하며 순차적이고 다량의 데이터를 입력할 때 주로 사용한다. 종류는 Vector, Arraylist, Linkedlist가 있다.

 

ArrayList

일반 배열과 ArrayList는 인덱스로 객체를 관리한다는 점에서 동일하지만, 크기를 동적으로 늘릴수 있다는 점에서 차이가 존재한다.

배열의 정적인 크기라는 한계점을 극복하기 위해서 탄생한 자료구조이다. 내부적으로 배열을 사용함에도 불구하고 배열리스트를 선언할때는 ArrayList는 사이즈를 초기화 시 사이즈를 표시하지 않는다.

 

길이에 대해 배열은 length 변수를 쓰고, ArrayList는 size() 메서드를 써야한다. 또한 ArrayList는 add()나 remove()와 같은 함수를 통해 변경이 가능하다.

 

또한 배열은 생성할 때 크기가 고정되어 있지만, ArrayList는 저장 용량(capacity)을 초과한 객체들이 들어오면 자동으로 저장용량이 늘어난다. 

기존의 Vector를 개선한 것으로 Vector와 구현원리가 기능적인 측면에서 동일하다. 그러나 Vector보다는 ArrayList를 사용할 것을 권하고 있다. (Vector는 호환성을 위해 남겨둠)

 

장점

• ArrayList와 Vector 같이 배열을 이용한 자료구조는 데이터를 읽어오고 저장할 때는 효율적

단점

• 용량을 변경해야할 때는 새로운 배열을 생성한 후 기존의 배열로부터 새로 생성된 배열로 데이터를 복사해야 해 비효율적

List<String> list = new ArrayList<>();
list.add("hello");
list.add("cat");
list.add("hi");
list.add("dog");
list.add("good");
list.add("friends");

System.out.println(list.size());   //  6
System.out.println(list.get(3));   //  dog
list.remove(3);
list.remove("cat");
System.out.println(list);   //  [hello, hi, good, friends]

ArrayList를 생성하고 런타임 시 객체들을 추가하는 것이 일반적이지만, 고정된 객체들로 구성된 List를 생성할 때도 있다.
이럴 때는 Arrays.asList(T... a) 메소드를 사용하면 된다.

List<String> companies = Arrays.asList("google", "apple", "samsung");
System.out.println(companies);  //  [google, apple, samsung]

List<Integer> numbers = Arrays.asList(1, 10, 100);
System.out.println(numbers);  //  [1, 10, 100]

시간복잡도

1) 원소 찾기 : O(1)
2) 마지막 노드에 원소 추가/삭제 : O(1) or O(N)
3) 마지막 노드 이외의 위치에 원소 추가/삭제하기 : O(N)
4) List의 크기 구하기 : O(N)

LinkedList

LinkedList는 각 노드(node)가 서로 연결되어 있는 형태이다. 배열(Array)은 구조가 간단하고 사용하기 쉽고, 데이터 조회 시간이 빠르다는 장점을 갖고 있지만, 크기를 변경할 수 없고, 비순차적인 데이터의 추가 또는 삭제에 시간이 많이 걸린다.

하지만 링크드 리스트는 불연속적으로 존재하는 데이터를 서로 연결(link)한 형태로 구성되어있다.

Array의 문제점을 해결하기 위한 자료구조가 Linked List이다.

 

링크드 리스트의 각 요소(node)들은 자신과 연결된 다음 요소에 대한 참조(주소값)와 데이터 구성되어있다.

 

장점

• 데이터 입력시 주소가 순차적이지 않아 요소를 메모리의 어느곳에나 둘 수 있음 (크기가 동적임)
• 인덱스 대신 현재 위치의 이전 및 다음 위치를 기억하는 형태로, 요소 중간에 삽입, 삭제 시 논리적 주소만 바꿔주면 되기 때문에 요소(데이터) 삽입,삭제가 용이

단점

• 요소에 바로 접근이 가능하지 않고 연결되어 있는 링크를 따라가야만 접근이 가능하여 접근속도가 느림

class Node {
    Node    next;   //  다음 요소의 주소 저장
    Object  obj;    //  데이터 저장
}

링크드 리스트에서의 데이터 추가, 삭제는 간단하다.

추가

A -> B -> D

• B 와 D 노드사이에 'C' 노드를 추가

1. C 노드 생성
2. B의 다음 노드 참조를 D -> C로 변경
3. C의 다음 노드 참조를 D로 적용

A -> B -> C -> D

삭제

A -> B -> C

• 'B' 노드 삭제

1. A의 다음 노드 참조를 B -> C로 변경

A -> C

중간에 데이터 추가/삭제의 경우 링크드 리스트가 배열보다 훨씬 나은 성능을 보여준다.

 

시간복잡도

1) 임의의 위치 원소 찾기 : O(N)
2) 마지막 노드에 원소 추가/삭제 : O(1)
3) 마지막 노드 이외의 위치에 원소 추가/삭제하기 : O(1)
4) List의 크기 구하기 : O(1) or O(N)

정리

컬렉션	읽기(접근시간)	추가/삭제	비고
ArrayList	빠름	느림	순차적인 추가/삭제는 더 빠름. 비효율적인 메모리 사용
LinkedList	느림	빠름	데이터가 많을수록 접근성 떨어짐