[자료구조] 배열과 list(LinkedList, ArrayList)

 

이번시간에는 배열과 list에 대해서 알아보겠습니다.

 

배열

 

• 크기가 정해져 있다, 따로 추가적인 기능이 없다
• 데이터에 대한 인덱스를 가지고 데이터의 인덱스를 변하지 않는다
• 인덱스를 사용하여 빠르게 데이터 조회가 가능하다
• 크기가 정해져 있기 때문에 추가적인 데이터를 넣을 수 없다
• 데이터를 삭제해도 크기가 줄어들지 않는다

        Object[] ary = new Object[4];
        
        ary[0]="something1";
        ary[1]="something2";
        ary[2]="something3";
        ary[3]="something4";

배열은 다수의 데이터를 그룹핑해서 효율적으로 관리할 수 있는 데이터 자료구조입니다. 위의 코드를 보시면  먼저 크기가 4인 배열을 선언했습니다. 

 

이런 배열의 가장큰 장점은 무엇일까요 ? 바로 인덱스입니다. 우리가 찾고자 하는 데이터가 어떤 인덱스에 있는지 만 안다면 우리는 그 데이터를 한번에 가져올 수 있습니다. 

 

반면에 배열의 단점은 크기가 고정되어있다는 것입니다. 위의 코드에서 배열의 크기를 4로 고정했기 때문에, 추가적으로 데이터를 삽입하는 경우 에러를 출력합니다. 처음 크기를 너무 크게 잡게되면 사용하지 않는 공간이 발생하게 됩니다. 그 외에도 배열의 크기를 생성할 때 지정하는 것, 배열의 엘리먼트를 알아내는 것도 불편합니다.

 

이런 배열의 단점을 보완해줄 수 있는 것이 리스트입니다.

 

 

리스트

 

• 처음, 중간, 끝에 데이터 삽입/삭제가 가능하다
• 데이터의 존재여부를 확인할 수 있다
• 모든 데이터에 접근할 수 있다
• 사용하지 않는 공간을 허용하지 않는다

리스트는 배열이 가지고 있는 인덱스라는 장점을 버리고 대신 빈틈없는 데이터의 적재라는 장점을 취한 데이터 스트럭쳐라고 할 수 있습니다. 쉽게말해서 배열의 기능을 좀 더 개선시킨 자료구조라고 생각하시면 됩니다.

 

만약 배열에서 데이터를 삭제하면 어떻게 될까요 ? 데이터를 삭제한다고 해서 배열의 크기가 줄거나 하지는 않습니다. 단지 해당 인덱스의 값을 사용하지 않을 뿐이죠. 하지만 리스트는 이런 사용하지 않는 공간을 허락하지 않습니다. 때문에 리스트의 모든 데이터는 사용가능한 데이터인거죠

 

• 자바스크립트

기본적으로 배열이 리스트의 기능을 가지고 있습니다.

numbers = [10, 20,30,40,50];
numbers.splice(3,1); // numbers 배열의 3번째 인덱스 삭제
for (i =0 ; i<numbers.length; i++){
    console.log(numbers[i]);
}

결과 : 
10
20
30
50

 

• c

c언어는 리스트를 지원하지 않고, 배열만을 지원합니다.

 

 

• python

리스트가 배열이며, 리스트는 크기가 가변적이고, 어떤 데이터 타입이든 저장할 수 있다. 대신 C의 array보다 메모리를 더 많이 필요로 합니다.

 

• java

자바는 배열과 리스트를 모두 지원합니다.

각각의 장점이 있기 때문에 상황에 맞게 유연하게 선택할 수 있습니다.

자바는 2가지의 리스트를 제공하며, (ArrayList, LinkedList) 각각의 특징을 상황에 맞게 잘 선택해야 합니다.

 

 

 

java로 개발할 때, 두가의 리스트의 성격을 잘 알고 사용해야 하는데, 이 둘의 차이점에 대해서 좀 더 알아보겠습니다.

 

(출처:http://www.nextree.co.kr/p6506/)

 

LinkedList는 node를 사용하며, 각각의 node는 데이터와 다음 node의 주소를 가지고 있습니다.

ArrayList는 내부적으로 배열을 사용하여 구현합니다.

 

 

-삭제

 

ArrayList,

5번째 값을 삭제하면 5번째 데이터를 삭제하고 6번째 부터 끝까지 데이터를 한칸씩 앞으로 이동해야 합니다.

LinkedList,

5번째 값을 삭제하면 단지 4번째 노드가 6번쨰 노드를 가리키게 하기만 하면 됩니다.

 

 

-삽입

 

ArrayList,

배열에서 처럼 해당 인덱스에 데이터를 넣을 수 있습니다. 하지만  공간이 필요한 경우, 추가적으로 공간을 늘려야 하는 연산이 필요하며, 리스트 가운데 삽입하는 경우 나머지 데이터들이 이동해야 합니다.

LinkedList,

처음, 중간, 끝 데이터가 어디 삽입되든 노드가 가리키는 주소만 변경해주면 됩니다.

 

-조회

 

ArrayList,

무작위 접근이 가능하기 때문에, 해당 인덱스의 데이터를 한번에 가져올 수 있습니다

LinkedList,

순차적 접근이기 때문에, ArrayList보다 더 많은 시간이 필요

 

 

정리해보면, 

ArrayList는 인덱스를 조회하는 경우 사용하는것이 좋고

LinkedList는 데이터의 삽입/삭제하는 경우 사용하는 것이 좋습니다.

 

(출처 : 생활코딩)

 

 

출처

https://wayhome25.github.io/cs/2017/04/17/cs-18-1/

https://velog.io/@imacoolgirlyo/List%EC%99%80-Array-%EC%B0%A8%EC%9D%B4

http://www.nextree.co.kr/p6506/