배열
기본적인 데이터 구조로 같은 타입의 변수들로 이루어진
유한 집합으로 정의됩니다.
배열을 구성하는 각각의 값을 배열 요소라고 하며,
배열에서의 위치를 가리키는 숫자는 Index라고 합니다.
int[] array;
int[] array = new int[5];
String[] array = new String[5];
int[] array = {1,2,3,4,5};
int[][] array2 = new int[3][4];
int[][] array2 = { {1,2,3,4},{5,6,7,8},{9,10,11,12} };
자바 배열 선언 예시
연속 리스트 (Contiguous List)
배열과 같이 인덱스를 통해 Value에 접근하며
배열처럼 연속적인 기억 장소에 데이터가 저장되는 자료구조이다.
말만 들어보면 똑같아 보이는데 배열과 연속 리스트의 차이점은 무엇일까?
-
배열은 데이터 삽입시 인덱스의 데이터를 덮어쓰는 형태로 삽입한다.
반면에 list에서는 삽입 되어지는 데이터를 한 칸씩 뒤로 밀고 해당 자리에 삽입한다.
-
배열은 데이터 삭제시 해당 데이터 인덱스는 메모리가 비어있는 상태가 된다.
반면에 list에서는 데이터가 삭제되고 뒤에 있는 데이터들이 앞칸으로 한 칸씩 전진하며 채워진다.
결과적으로 배열에서는 메모리의 낭비를 초래하며
연속 메모리를 효율적으로 관리하는 구조가 된다.
연결 리스트 (Linked List)
연속 리스트와 다르게 가장 큰 특징은 메모리의 각 부분에 다음 순서의 데이터를 가리키는 포인터(Pointer)가 존재한다는 것이다.
(출처 https://yjg-lab.tistory.com/118)
데이터와 포인터를 합쳐서 노드(Node)라고 말하는데
이 모양은 마치 기차와 같다
기차의 각 화물칸은 연결고리를 통해서 앞칸 혹은 뒷칸과 연결된다.
이러한 포인터로 연결 리스트가 얻는 이점은 다음과 같다.
-
단순히 노드의 point가 가리키는 것을 바꾸는 것으로 데이터의 추가, 삽입 삭제가 가능하다.
예컨데 앞서 말한 Contiguous List에서는 데이터를 중간에 넣을 시에 뒷 칸의 데이터를 모두 뒤로 미뤄야 했지만 연결리스트는 그냥 서로의 연결 고리를 끊고 새로 들어온 데이터에 연결 고리를 묶어주면 되는 것이다.
