java - 배열과 리스트

출처 : 어라운드 허브 스튜디오 출처

배열과 리스트

배열

정의

같은 데이터 타입의 변수들을 순차적으로 저장하기 위한 자료 구조

인덱스의 개념을 가지며 0부터 시작

각 인덱스에 데이터들이 매치되어 처리하기 용이함

인덱스는 고유번호의 느낌(pk같은)

한번에 많은 메모리 공간 선언이 가능함

크기가 정해져 있음

삭제된 공간이 그대로 남음 => 메모리 낭비 가능성 존재

// 선언 예시
int[] arrary;
String[] array;
double[] array;

// 배열 생성 예씨
array = new int[10]; // 10칸 짜리
array = new char[1000];
array = new String [5];

array = {0, 1, 2, 3};
array = {'a', 'b', 'c'};

// 배열 선언과 생성 예시
int[] array = new int[10];


// 2차원 배열
int[][] array = newint[2][7];

// 비정방형 배열, 향과 열의 개수가 다름
int[][] array = new int[3][];
array[0] = new int[3];
array[1] = new int[4];
array[2] = new int[10];

// ArrayList : 배열의 크기를 예상하기 힘들 경우 사용하기 좋은 클래스. 크기를 가변적으로 사용할 수 있음 => 리스트임

리스트

배열의 한계 때문에 만들어진 자료형
배열 사용을 위해서 크기를 지정해야 함
=> 하지만, 프로그래밍 중 동적으로 생성하는 경우가 많기 때문에 크기를 미리 정할 수 없음.
=> List는 메모리가 허용하는 한 계속해서 추가할 수 있도록 만든 자료형 클래스임
리스트에서의 인덱스는 몇번째 데이터인가 정도의 의미를 가짐

List 와 ArrayList 존재

• List

• ArrayList

  • List 인터페이스를 상속받은 클래스 중 하나
    - 배열과 동일하게 0부터 인덱스 시작
  • 내부적으로 저장가능한 메모리 용량(Capacity) 존재, 그 이상을 저장하려 할 때 새로운 메모리 할당

• 메서드

  • Add : 자료를 넣을 때 사용
  • Get : 데이터 가져올 때 사용
  • Size : List 길이 return
  • Contains : List에 있으면 True 없으면 False
  • Remove : remove(삭제) / 성공시 true else false

• LinkedList

  • 내부적으로 양방향 연결 리스트로 구성되어 있어 참조하려는 원소에 따라 처음부터 정 or 역방향으로 순회 가능
  • 순차적으로 접근함 => 검색의 속도가 느림

ArrayList vs LinkedList

조회

• ArrayList

  • 각 데이터의 index를 가지고 있음 + 무작위 접근 가능 => 해당 index의 데이터를 한번에 가져올 수 있음

• LinkedList

  • 순차적으로 접근하므로 검색의 속도가 느림

데이터 삽입 / 삭제

• ArrayList

  • 데이터 삽입, 삭제시 그만큼 위치를 맞춰줘야 함

    • ex) 크기 N의 ArrayList에서 두 번째 인덱스 삭제 시 3번째부터 N번째 데이터의 인덱스를 한 칸씩 이동해야 함

  • 따라서, 삽입과 삭제가 많을시 불리함

• LinkedList
  • 데이터 추가, 삭제 시 가리키고 있는 주소값만 변경해주면 됨

시간복잡도

출처