/ POSTS

Java의 Array에 대해 알아보기

Note : 이 글은 지극히 주관적인 생각을 토대로 작성된 글입니다. 혹시나 잘못된 부분이 있다면 메일 또는 코멘트를 통해 알려주시면 감사하겠습니다. 😄 제 메일은 About 탭에서 확인하실 수 있습니다. 📧

P.S : 이 페이지는 웹에 최적화 된 페이지입니다. 가급적 모바일이 아닌 웹에서 보시는 것을 추천드립니다.

배열(array).

  • 연속된(contiguous) 메모리 공간 차지, 인덱스(index)로 위치 식별
int n[] = new int[100];
n[0]=5;
n[1]=8;
n[2]=4;

배열 내 임의 위치 자료 접근 시간 : O(1)

  • 인덱스 0 위치 자료 접근 시간: 8000+0*4 -> 덧셈 1회, 곱셈 1회

  • 인덱스 1 위치 자료 접근 시간: 8000+1*4 -> 덧셈 1회, 곱셈 1회

  • 인덱스 2 위치 자료 접근 시간: 8000+2*4 -> 덧셈 1회, 곱셈 1회

  • …

  • 인덱스 n-1 위치 자료 접근 시간: 8000+(n-1)*4 -> 덧셈 1회, 곱셈 1회

  • 배열 내 자료 위치에 무관하게 항상 일정한 시간 소요

배열 첫 위치 자료 삽입: O(n)

  int n[] = new int[10];
  for (int i = 0; i < 5; i++) 
    n[i] = i + 1;

연결리스트(linked list)

  • 연결리스트 내 임의 위치 상수 시간 접근 불가.

  • k번째 자료 접근 위해 head부터 k번 다음 자료 위치로 이동 필요.

LinkedList<Integer> list = new LinkedList<>();
list.add(5);
list.add(8);
list.add(4);

연결리스트 내 임의 위치 자료 접근 시간: O(n)

  • 위치 자료 접근 시간 : 1

  • 위치 자료 접근 시간 : 2

  • 위치 자료 접근 시간 : 3

  • …

  • 마지막 n번째 위치 자료 접근 시간: n

  • 최악의 경우 n번 이동 필요: O(n)

  • 배열 내 자료 위치에 무관하게 항상 일정한 시간 소요

연결리스트 첫 위지 자료 삽입 : O(1)

LinkedList<Integer> list=new LinkedList<>();
list.add(1);
list.add(2);
list.add(3);
list.addFirst(7);