[자료구조] 배열과 리스트 +ArrayList, LinkedList

이 글은 생활코딩 자료구조 수업을 기초로 정리한 글입니다.

opentutorials.org/module/1335

 

 

 

배열

 

 

1. 배열이란?

 

 : 데이터를 그룹핑해서 관리하는 자료구조

 

 

보통 group으로 나누는 행위는 보다 체계적인 관리를 위해서 진행합니다

블로그에 글을 쓸때도 카테고리 없이 글을 쓰면 나중에 글이 50개가 되고 100개가 되었을때 관리가 되지 않습니다. 하지만 카테고리를 나누어서 관리하면 보다 원하는 글을 빠르게 찾을 수 있고 체계적인 관리가 가능합니다.

 

 

2. Index

 

배열에서 각 요소는 index라는 값을 가지고 있습니다.

 

index는 그룹화된 데이터 안에서 개별 데이터를 식별하게 해주는 역할을 합니다.

즉, index를 활용해서 배열의 데이터를 가져오고 저장할 수 있는 것입니다.

 

 

(배열의 한계)

배열에서는 안타깝게도 새로운 데이터를 추가할 수가 없는데요.(수정, 삭제는 가능)

 

"그렇다면 배열의 처음, 중간, 끝에 데이터를 추가하기 위해서는 어떻게 해야할까요?"

 

"list"를 사용합니다.

 

 

 

 

 

 

List

 

 

1. List란?

 

리스트는 배열과 같이 그룹화된 자료구조이지만 순서가 있습니다.

배열의 index도 순서가 있지만 배열의 index는 위치를 나타내는 개념이 강합니다.

즉, 배열의 index는 유일무이한 식별자라면 리스트의 index는 '몇번째 데이터인가' 의 개념입니다.

 

 

 

2. '처음, 중간, 끝에 데이터를 추가할 수 있다'

 

배열과 리스트의 가장 큰 차이점은 바로 이 기능입니다.

아래의 그림을 보면 쉽게 이해가 될 것입니다.

 

출처 : 생활코딩

 

 

 

 

 

그럼 arrayList는 뭔가요?

 

"array를 활용해서 만든 list입니다."

 

list를 만드는 방법은 여러가지가 있습니다.

 

array를 활용해서 만들수도 있고 

linked방식으로 만들 수도 있습니다.

(또 다른 방식으로도 만들 수 있습니다.)

 

 

 

ArrayList vs LinkedList

 

결론부터 말씀드리면

 

배열에 대한 추가, 삭제 기능이 필요하지만 주 용도가 "조회"라면 : ArrayList

 

배열에 대한 추가, 삭제가 빈번히 일어나는 경우 : LinkedList

 

출처: 생활코딩

 

 

ArrayList

arrayList는 array의 중요 특성인 index라는 특성을 이용해서 데이터를 접근 및 조작합니다.

이 index를 활용하면 해당 index의 element 값을 바로 반환해줄 수 있는 장점이 있습니다.

하지만 배열은 메모리에 일렬로 저장되기 때문에 추가 및 삭제시 해당 인덱스 뒤에 있는 모든값들을 당겨주거나 밀어줘야합니다. (즉, 추가 삭제시 많은 비용이 듭니다.)

 

 

LinkedList

LinkedList는 array처럼 메모리에 일렬로 정렬되지 않습니다.

하나의 "노드라는 객체로 구성되며 객체는 본인의 값과 다음 값에 대한 정보를 가지고 있습니다."

그렇기 때문에 추가, 삭제시 앞, 뒤 노드의 정보만 바꿔주면 됩니다.(그 뒤의 데이터를 당기거나 밀어줄 필요가 없습니다.)

하지만 조회시 head부터 찾아가야 하기 때문에 시간이 상대적으로 오래걸립니다. 

 

 

 

 

 

 

 

 

언어별로 지원하는 자료구조가 다릅니다.

 

예를들어, c언어의 경우 언어 자체적으로 list를 지원하지 않습니다 그렇기 때문에 list에 대한 이해가 꼭 필요하고 이를 구현해서 사용할 줄 알아야 합니다.

 

python은 리스트를 기본적으로 지원하고 배열과 리스트의 구분이 없습니다.

이는 사용자가 자료구조가 뭔지 몰라도 사용할 수 있게 한 것입니다.

 

 

'그렇다면 제가 주력으로 쓰는 kotlin의 경우는 어떨까요?'

 

kotlin은 기본적으로 배열 리스트 모두 지원합니다.

또,  리스트를 list와 mutableList로 구분하고 있습니다.

List : 읽기 전용으로 쓰임

mutableList(=arrayList) : 추가, 삭제가 필요하고 조회가 빈번히 사용될때 (일반적인 list의 개념)

LinkedList : 추가, 삭제가 빈번히 사용될때

 

 

이렇게 코틀린은 파이썬과 다르게 다양한 자료구조를 제공해주며 사용자에게 다양한 선택권을 줍니다.