Arraylist(어레이리스트) 핵중요한 특징 3가지!!

Arraylist(어레이리스트) 핵중요한 특징 3가지!!

 

 

안녕하세요.

 

로스윗의 코딩캠프입니다.

 

오늘부터는 지난 시간에서 말씀드린대로 본격적으로 자료구조 포스팅을 시작하겠습니다.

 

가장 쉽고 만만한 어레이리스트(arraylist)부터 출발해볼까요~? ㅎㅎ

 

 

 

 

 

 

- List(리스트)란?

리스트(List)는 선형적인 자료구조로 데이터를 일렬로 늘여놓은 형태를 가진 자료구조를 얘기합니다.

일렬로 늘여 놓았기 때문에 데이터간에 순서가 있다는 점이 List의 특징입니다.

 

리스트(list)는 크게 어레이리스트(ArrayList)와 링크드리스트(LinkedList)로 구분을 할 수 있고

 

그리고 LinkedList는 데이터간의 연결 방식에 따라서 다시

 

Single Linked List와 Double Linked List로 구분을 할 수 있습니다.

이번 시간에는 ArrayList에 대해서 한 번 살펴보도록 하겠습니다.

 

 

 

- 어레이리스트(Arraylist)

arraylist는 배열 기반이기 때문에 배열과 동일한 방법으로 인덱스를 사용하게 됩니다.

그리고 이 인덱스틑 통한 데이터 접근은 Random access 방식이기 때문에

 

list의 데이터가 100개가 있든 1000개가 있든 혹은 1억개가 있든

 

인덱스만 알고 있다면 항상 동일한 시간을 소요해서 데이터에 접근을 할 수 있습니다.

 

이건 배열의 가장 큰 특징 중 하나입니다.

 

 

 

배열 기반의 어레이리스트(arraylist)

 

그리고 arraylist는 컴퓨터의 실제 물리적인 메모리공간에서도

 

연속적인 공간을 사용하기 때문에 컴퓨터가 연산하기 쉬운 구조를 가지고 있습니다.

그렇기 때문에 0번에서 1번 인덱스, 1번에서 2번 인덱스

 

이런식으로 이전 인덱스에서 다음 인덱스로 접근하는 속도가 빠릅니다.

반면, LinkedList는 데이터를 논리적으로 연결을 시켜서

 

마치 연속된 형태의 데이터처럼 쓸 수 있도록 구현은 되있지만

실제 컴퓨터 메모리상에서는 물리적인 공간을 연속적으로 차지하고 있는 형태가 아닙니다.

그렇기 때문에 데이터간의 이동 자체에는 시간이 더 소요됩니다.

 

 

 

- Arraylist 연산 3가지

ArrayList에서 중요한 연산은 총 3가지가 있습니다.

 

데이터 삽입하기, 데이터 삭제하기, 데이터 탐색하기 입니다.

이 Arraylist에 데이터를 삽입하는 연산을 한 번 더 자세히 보도록 하겠습니다.

 

 

arraylist 데이터 삽입하기

 

-arraylist 데이터 삽입하기

우선 배열은 선언을 해보셨으면 아시겠지만 고정된 크기의 공간을 할당을 받습니다.

위 그림에서는 6칸의 공간을 할당받아서 0번부터 5번까지의 인덱스가 있는 배열을 나타냈습니다.

그리고 0번인덱스부터 2번인덱스까지 총 3개의 데이터가 들어가 있는 상태입니다.

 

 

여기서 데이터를 추가 삽일을 하게 된다면

 

마지막 데이터 바로 다음인 3번 인덱스에 데이터가 삽입이 될 것입니다.

이렇게 추가 동작은 데이터가 있는 위치에서 가장 뒤에 데이터를 삽입하게 되지만

 

데이터를 중간에 삽입하는 경우도 있을 수 있습니다.

 

arraylist 데이터 삽입하기 그림 예시

예를들면 그림처럼 0번부터 3번까지 데이터가 들어가 있는 상태에서

 

2번의 위치에 데이터를 삽입하고 싶을 수 있습니다.

이런 경우는 삽입하고자 하는 인덱스의 위치로부터

 

데이터가 위치한 제일 뒤의 인덱스까지

 

모두 한칸씩 뒤로 밀어주는 작업을 먼저 해야 합니다.

 

 

arraylist 데이터 삽입하기 그림 예시

인덱스 위치로부터 뒤에 있는 데이터가 지금은 2개가 있죠.

만약에 뒤에 데이터가 한 개라면은 데이터를 옮겨주는 연산을 한 번 하면 되겠지만

이렇게 데이터가 두 개인 경우에는 두 번을 해야 하구요

데이터가 1000개라면 1000번, n개 라면 n번 데이터를 옮겨주는 연산을 해야하기 때문에

시간 복잡도는 O(N)이 됩니다.

 

arraylist 데이터 삽입하기 그림 예시

 

그렇게 데이터를 한칸씩 뒤로 밀어주는 작업을 한 뒤에

인덱스 칸에 해당하는 위치에 데이터를 삽입하면 되겠죠.

만약 데이터를 한 칸씩 뒤로 미루지 않고 그대로 데이터를 넣어버리면 어떻게 될까요?

기존 인덱스 칸에 있던 노란색 데이터가 소실이 됩니다.

 

 

 

- Arraylist 데이터 삭제하기

그 다음으로 이제 인덱스 기반의 데이터 삭제를 할 때도 데이터를 이동시켜주는 작업을 해야 합니다.

예를 들어서 2번 위치에 있는 인덱스의 데이터를 삭제하고 그냥 둔다면

 

이렇게 중간에 데이터가 뻥 뚫린 상태가 되겠죠.

 

arraylist 데이터 삭제하기 그림 예시

 

그렇기 때문에 뒤에 있는 데이터들을 한 칸씩 앞으로 당겨오는 작업을 해줘야 합니다.

마찬가지로 여기서도 인덱스 위치로부터 뒤에 있는 데이터가 많으면 많을수록

 

이동시켜야 하는 데이터의 양이 많아지기 때문에 처리시간이 길어지게 됩니다.

따라서 데이터의 양과 처리시간이 비례한 시간복잡도 O(N)을 갖겠죠.

 

 

 

arraylist 데이터 삭제하기 그림 예시

 

그래서 그림처럼 빈공간없이 리스트안에 데이터들이 연속적으로 나열될 수 있도록 처리를 해줍니다.

 

 

 

- Arraylist 데이터 탐색하기

마지막으로 Arraylist에서 인덱스를 통한 데이터 탐색은

 

앞에서 말씀 드린 것처럼 Random access로 해당 위치에 다이렉트로 접근하게 됩니다.

그렇기 때문에 데이터가 아무리 많아져도 한번에 해당 위치에 접근해서 데이터를 가져올 수 있기 때문에 

 

인덱스를 통한 데이터 탐색 속도는 매우 빠릅니다.

이렇게 데이터의 개수와 상관없이 연산의 속도가 일정하다면

 

이런경우는 시간 복잡도 O(1)이라고 하게 되죠.

뒤에서 LinkedList에서도 다루겠지만 LinkedList는 이런 방식의 접근이 불가능합니다.

 

 

 

- 정리 및 요약

자료 구조를 공부할때 중요한 것은 

 

첫번째로 각 자료구조의 특징과 장단점 아는 것입니다.

두 번째는 시간복잡도나 특징을 단순히 외우는게 아니라 

 

왜 시간복잡도가 O(N)이고 O(1)인지, 또 느리다면 왜 느리고 빠르다면 왜 빠른지를 이해하는 겁니다.

그리고 자료구조는 직접 구현해보는 것이 가장 이해하기 빠른 방법이기 때문에

 

자바로 한번 구현해 보시는 것을 추천드립니다.

 

긴 글 읽어주셔서 감사합니다.

 

다음 포스팅에서 다시 뵙겠습니다.

 

코딩 캠프는 미래의 개발자인 여러분과 함께합니다.

 

모두 화이팅!

 

개발자 여러분, 빅오표기법이 헷갈리신가요? 확실하게 알려드리겠습니다!

개발자 여러분, 빅오표기법이 헷갈리신가요? 확실하게 알려드리겠습니다!

개발자가 자료구조와 알고리즘을 알아야 하는 진짜 이유

개발자가 자료구조와 알고리즘을 알아야 하는 진짜 이유