Array와 ArrayList 그리고 LinkedList

우리가 프로그래밍을 접하면서 한번쯤은 들어봤을 단어인 Array 그리고 ArrayList와 LinkedList 이것들이 무엇인지

장점과 단점은 뭐고 주로 어디에 쓰이는지 알아보도록 하자

 

 

 

 

Array

---

Array는 흔히들 알고있는 배열이다

같은 타입의 데이터를 여러개 저장해야할때 순서대로 값을 저장하며, 중복을 허용한다

또한 index를 이용해서 특정위치에 있는 데이터를 얻을수있으며, 속도가 빠르다는 장점을 가진다

그리고 1차원, 2차원 같이 다차원 배열을 사용할수있다

 

 

 

위사진은 배열을 그림으로 좀더 쉽게 분석한것인데

배열의 크기를 10으로 잡으면 첫 index는 0부터 시작해서 9까지 총 10개의 공간이 만들어진다 length는 10이며 index를 이용해서 해당공간에 있는 데이터를 쉽게 찾아낼수 있다

 

이처럼 배열은 선형 자료구조로써, 같은타입의 데이터들이 연속해서 위치한다는 것을 알수있다

자바에서 배열을 할당하는 방법은 여러가지 방법이있는데

 

int[] array = new int[5] // 배열의 선언과 동시에 크기를 할당한다
int[] array = {1,2,3,4,5} // 배열의 선언과 동시에 크기를 할당하고 초기화한다

 

우리가 배열에 대해서 가장 중요하게 생각해야할점은 장점과 단점을 명확하게 아는것이다

다시한번 배열에 장점에 대해서 말해보자면 우선 속도가 빠르다는 것이다

왜냐하면 메모리상에 순서대로 차곡차곡 쌓이기 때문에 데이터를 읽기에 무척 용이하다

그리고 원하는 데이터를 쉽고 빠르게 얻을수있는데 이는 우리가 학교에서 학번을 정해주듯이 데이터에도 index라는 번호를 매겨 해당되는 데이터의 index만 알면 데이터를 쉽게 조회할수 있다

 

또한 참조를 위한 추가적인 메모리를 잡아먹지 않는다는 것인데 이는 LinkedList에 대해서 알게되면 자연스럽게 습득할수있다

 

 

---

반응형

---

 

 

 

이번에는 배열의 단점에 대해서 알아보자

첫번째로 배열의 크기를 한번 선언하게되면 다시 크기를 바꿀수없다

우리가 코드상에서 배열을 선언하고 안에 크기를 할당해주면 메모리에 우리가 선언한 그 크기만큼 공간이 할당되며, 그배열은 크기를 더이상바꿀수없다

 

추가적으로 데이터가 들어올려면 데이터를 하나 삭제하거나 아니면 새로운 크기의 배열을 할당해주는 방법밖에없다

이때문에 배열을 넉넉하게 잡으면 메모리가 낭비되고, 적게잡으면 데이터를 집어넣고싶어도 공간이없는 불상사가 발생할수있다

 

그다음으론 배열의 엘리먼트(index와 데이터)가 지워지게 되면 그곳이 빈곳으로 남는다는 단점을 가지고있는데

이는 index와 데이터가 맞아야 하기 때문에 엘리먼트가 지워지게되면 그곳을 빈곳으로 두고 메모리를 쓸데없이 잡아먹게된다

 

단점을 정리하자면 크기변경불가, 데이터의 삽입, 삭제불리, 메모리재사용 불가능으로 정리할수있겠다

Array(배열)의 특징을 알아보았으니 이번에는 ArrayList에 대해서 알아보도록 하자

 

 

 

 

 

 

 

 

ArrayList

---

 

ArrayList를 알아보기전에 Collection Framework(컬렉션 프레임워크)에 대해서 알고있으면 매우좋은데

여기서는 우선 ArrayList의 특징을 말하는것이니 혹시 컬렉션 프레임워크에 대해서 알고싶다면 여기를 클릭해보도록 하자

 

ArrayList는 컬렉션 프레임워크중 List 인터페이스를 구현한 하나의 구현체로써 위에서 말한 Array(배열)을 기반으로 한 구조를 가지고있다

 

이게 무슨말이냐면 ArrayList는 Array와 동일한 메커니즘을 가지고있는데 index를 가지며, 조회가 빠르고, 연속적으로 데이터들이 위치해있다

하지만 Array와 가장큰 특징으로는 가변이라는 것이다

 

Array(배열)은 한번 크기가 할당되면 그 크기를 바꿔줄수없지만 ArrayList는 가변이라서 크기가 넘어가도 넘는 크기만큼 메모리를 재할당해준다

이는 Array와 가장큰 특징으로써 컴파일이 되면 더이상 크기를 바꿀수없는 Array에 반해 컴파일이 끝나도 크기를 유동적으로 변경할수있다

 

 

 

그다음은 List의 특징이기도 한데 List는 빈틈없는 데이터를 적재를 하기위해서 나온 자료구조인만큼 빈 엘리먼트를 허용하지않는다

Array같은 경우는 중간에 엘리먼트가 삭제될경우 빈엘리먼트가 만들어졌지만 ArrayList같은경우는 만약 삭제가 일어날경우 순서를 보장하기위해서 한칸씩 앞으로 당기게된다

이 과정에서 O(N)이라는 시간복잡도가 발생하게되며 데이터가 커질수록 한칸씩 당기게되는 데이터의양도 급격하게 늘게된다

 

정리하자면 Array와 ArrayList의 가장큰특징은 동적이냐, 정적이냐의 차이와 Array는 빈엘리먼트를 허용한다(물리적 저장소와 index를 맞춰야하기때문에)

그다음 ArrayList는 List의 구현체중 일부이기떄문에 빈엘리먼트를 허용하지않고 중간에 값을 삽입, 삭제하게되면 그만큼 데이터가 밀려나거나 당겨지게된다

 

 

 

 

 

 

 

 

LinkedList

---

LinkedList같은 경우에는 ArrayList와 구조자체가 다르다고 볼수있는데

우선 ArrayList는 위에서 계속 언급했듯이 조회는 빠르지만 삭제, 삽입에는 불리하다 하지만 LinkedList같은 경우에는 ArrayList와는 정반대의 특성을 가지고있는데

 

조회는 ArrayList보다는 느리지만 삭제, 삽입은 LinkedList보다 빠르다

 

 

위에 사진은 LinkedList의 구현방식인데 우선 첫번째로 시작하는 데이터가 그다음데이터를 참조한다(가르킨다)

그다음 두번째데이터는 그다음데이터를 가르키고 세번째데이터는 그다음데이터를 가르켜서 계속 링크되어 데이터를 가르킨다

 

Array에서 말한 참조를 하기위한 메모리를 낭비하지않는 다는것이 여기서 나오는데

LinkedList같은 경우에는 추가로 참조하는 포인터가 존재하고, 이러한 특징때문에 중간값을 조회하려면 Array에서는 인덱스를 찝어서 조회하는 것과는 다르게 LinkedList는 해당되는 데이터가 나올때까지 거슬러 올라가게된다

 

이러한 구조를 가지는덕분에 조회에는 ArrayList보다는 느려도 삽입이나 삭제는 빠르다

만약 두번재 데이터를 삭제하게되면 간단하게 첫번째 데이터가 세번째 데이터를 가르키면 끝이다

또한 삽입이 첫번째와 두번째 데이터 사이에 삽입이 일어나게되도 첫번째 데이터가 새로들어온 데이터를 가르키고

새로 들어온 데이터는 두번쨰 데이터를 가르키게 되면 ArrayList나 Array와는 다르게 빠르게 끝낼수있다

 

 

정리하자면 ArrayList와 LinkedList의 가장큰 차이점으로는 ArrayList는 조회는 빠르지만 삽입과 삭제는 비교적 느리다

LinkedList는 조회는 비교적 느리지만 삽입삭제에는 빠르다는것을 알수있다