목차
- 순서대로 저장
- 중복을 허용
- 비어있는 데이터(null)를 허용하지 않는다.
- 처음, 끝, 중간에 element를 추가/삭제하는 기능이 포함되어야 함.
For each Languages
최근의 프로그래밍 언어는 리스트를 기본적으로 지원한다. 비교적 오래된 언어의 경우 리스트를 지원하지 않기도하다.
C는 list를 지원하지 않는다. 따라서 개발자가 직접 리스트를 구현해야 한다.
Python은 리스트를 지원하지만 배열을 지원하지 않는다.
- 하지만 List는 Array라고도 볼 수 있기 때문에 자바만큼은 아니지만 리스트를 이용하여 배열처럼 사용할 수 있다(?)
Java 는 엄격하게 배열과 리스트를 구분한다.
Array :
int[] numbers = new int[10];List :
ArrayList numbers = new ArrayList();Java API 호출 필요
import java.util.ArrayList;
Java에서 List는 ArrayList와 LinkedList로 다시 나뉘어진다.
ArrayList와 LinkedList에 대해서도 알아보자.
결과적으로 데이터 스트럭쳐는 모든 언어마다 다르다는 것이다. 따라서 각각의 언어에 맞게 개발자의 선호에 맞게 데이터 스트럭쳐를 구현해서 사용할 수 있다.
Array vs List
Insert
출처 : 생활코딩
- Array에선 기존에 존재하는 element의 index에 다른 value를 삽입하면 기존 value를 덮어씌우는 방식으로 데이터가 추가된다. 새 값은 이식되었지만, 기존의 값은 사라졌으므로 length는 그대로 유지된다. 사실 Array는 애초에 크기를 변경할 수 없는 자료구조이기도하다.
- List에서는 기존의 index의 element가 뒤로 밀리면서 새로운 element가 그 사이에 삽입된다. Array처럼 기존의 값에 덮어씌어진게 아니라 추가되었으므로 전체 데이터의 length가 증가한다.
Remove
출처 : 생활코딩
- Array에선 element를 삭제하면 해당 element가 null로 유지된다.
따라서 해당 인덱스에 value(실제 데이터)가 있는지 없는지에 대한 체크가 필요하다. (메모리 누수 가능성) - List에선 element를 삭제하면 뒤의 index의 element가 앞으로 당겨온다.
모든 데이터가 연속되어지므로 null이 존재하지 않는다. 때문에 데이터를 추가/삭제 할 때 데이터가 있는지 여부를 체크할 필요가 없다. - 이를 바탕으로 Array와 List에서 index의 의미가 다르게 해석된다.
- List에서 index는 몇 번째 데이터 인지를 알려주는 정도라면,
- Array에서 index는 그 값 자체를 의미하는 식별자가 될 수 있다.
아직 정리하지는 않았지만, List에는 ArrayList와 LinkedList가 있는데, 둘을 비교해보았다. 그냥 이렇다는것만 알아두고 다음 포스트로 넘어가서 ArrayList에 대해 정리한 글을 읽어보도록 하자.
ArrayList vs LinkedList
출처 : 생활코딩
인덱스 조회
ArrayList는 데이터 탐색 시, 메모리에 적재된 Array의 주소에서 Index를 통해 상대적인 위치를 찾아서 주소를 전달하기 때문에 빠르다.
반면 LinkedList는 HEAD에서 부터 연결된 다음 노드를 하나씩 찾아가야 하기 때문에 탐색 속도가 느리다는 단점이 있다.
데이터 관리 (추가/삭제)
ArrayList에서 데이터를 추가하기 위해서는 새로운 데이터가 추가될 인덱스의 element부터 뒤의 모든 데이터를 뒤로 밀어서 빈 값을 만들어내고, 그 빈 값에 새로운 데이터를 추가하는 방식이다. 삭제하는 방법 역시 데이터를 삭제하면, 뒤의 모든 데이터를 삭제한 데이터만큼 앞으로 당겨와야 한다. 이 때문에 추가/삭제시 느리다는 단점이 있다.
반면 LinkedList는 element가 연결된 앞 뒤의 노드의 주소값만 변경하면 되기 때문에 ArrayList와 비교해서 훨씬 빠르다는 장점이 있다.
본격적으로 ArrayList는 다음 포스트에서 정리했다.
자료구조 글 목록
- 자료구조-배열 (이전글)
- 자료구조-리스트 (현재글)