배열과 링크드리스트

배열이란?

• 배열(Array)은 각 값에 대해 별도의 변수를 선언하는 대신, 여러 값을 하나의 변수에 저장하는데 사용되는 것!
• 배열을 선언하려면 대괄호를 사용해 변수 유형을 정의하여 사용해준다
• 배열은 고정된 갯수의 데이터만큼 연속된 공간에 저장하는데 사용하는 자료구조로써, 배열의 길이는 배열이 생성될 때 설정 가능
  한 번 생성된 배열의 길이는 변경할 수 없음!
• 배열의 각 항목을 요소라고 하며, 각 요소는 숫자 인덱스를 사용해 접근 할 수 있음
• 맨 첫 번째 요소는 0부터 시작하는 걸 잊지말자!
• 연관된 데이터를 저장하기 위한 변수의 선언을 줄여주고, 반복문 등을 사용해 계산과 같은 과정을 쉽게 처리 가능
• 데이터를 추가하거나 삭제할 때는 효율적이지 못함

---

LinkedList(링크드리스트)란?

• Collection 프레임워크의 일부이며 java.util 패키지에 소속
• LinkedList 클래스는 데이터가 연속된 위치에 저장되지 않고, 모든 데이터가 데이터 부분과 주소 부분을 별도로 가지고 있음
• 데이터는 포인터와 주소를 사용하여 연결
• 각 데이터는 '노드' 라고 불리며 배열에서 자주 삽입, 삭제가 이루어지는 경우에 사용하는 것이 용이해 ArrayList보다 선호되어 사용한다
• 하지만 ArrayList 보다는 검색이 느린 단점이 있음
• 다양한 형태로 타입을 셋팅하여 선언 가능 (Class, integer, String, Character 등의 타입으로 선언 가능)

// 타입 설정 X, Object로 입력
LinkedList li = new LinkedList();

// List 타입을 LinkedListDemo
LinkedList<LinkedListDemo> demo = new LinkedList<LinkedListDemo>();

// int 타입 선언
LikedList<Integer> i = new LinkedList<Integer>();

// 타입 선언 생략
LinkedList<Integer> i2 = new LinkedList<>();

// 초기 값 셋팅
LinkedList<Integer> i3 = new LinkedList<Integer>(Arrays.asList(1, 2, 3));

// String 타입 사용
LinkedList<String> st = new LinkedList<String>();

// Char 타입 사용
LinkedList<Character> ch = new LinkedList<Character>();

---

Array vs LinkedList

• Array는 연속된 메모리 공간에 존재, LinkedList는 메모리 상에서 떨어져 있는 데이터들이 앞, 뒤의 데이터를 기억하는 형태로 존재
• Array 저장 데이터 조회 = O(1), LinkedList = O(N)이 소요
• 데이터 추가 및 삭제 시 Array  = O(N) 소요, LinkedList = O(1) 소요
• Array는 컴파일 과정에서 메모리가 할당되는 정적 메모리 할당, LinkedList는 런타임 환경에서 메모리가 할당되는 동적 메모리 할당
• Array는 Stack 영역에 메모리 할당, LinkedList는 Heap 영역에 할당