[Data Structure] List

List

---

Array와 List의 차이점

배열의 가장 큰 특징은 인덱스가 있다는 것이다. 만약 인덱스를 알고 있다면 인덱스를 이용해서 데이터를 가져 올 수 있다.

인덱스를 이용한 데이터의 조회는 매우 빠르게 처리된다. 하지만 인덱스를 이용해서 데이터를 가져오려면 데이터에 대한 인덱스의 값이 고정되어야 한다.

자연스럽게 어떤 엘리먼트가 삭제되면 삭제 된 상태를 빈 공간으로 남겨둬야 하며, 이것은 메모리의 낭비를 초래한다.

또한 배열에 데이터가 있는지 없는지를 체크하는 로직이 필요하기도 한다.

리스트는 배열이 가지고 있는 인덱스라는 장점을 버리고 대신 빈틈없는 데이터의 적재라는 장점을 취한 데이터 스트럭쳐라고 할 수있다.

삭제

1. 배열

데이터를 순회하는 과정에서 3번 데이터가 있는지 없는지 체크 해야한다.

삭제 한 경우에도 3번 공간은 사라지지 않기 때문에 메모리 공간을 낭비하게 된다.

2. 리스트

앞에 있는 데이터가 삭제되면 앞으로 땡겨?진다.

List의 기능

● 처음, 끝, 중간에 엘리먼트를 추가/삭제 하는 기능

● 리스트에 데이터가 있는지를 체크하는 기능

● 리스트의 모든 데이터에 접근 할 수 있는 기능

언어 별 List

언어	List
C	List 지원 안함
JavaScript	배열이 리스트
Python	리스트가 배열
Java	독립 된 문법으로 모두 제공

※ 최근의 언어는 리스트를 기본적으로 지원한다.

※ Java

//배열
int[] numbers = {10,20,30,40,50};
 
//리스트 2개를 지원
//ArrayList
ArrayList numbers = new ArrayList();
numbers.add(10);
numbers.add(20);
numbers.add(30);
numbers.add(40);
numbers.add(50);
numbers.remove(3);
System.out.println(numbers);
 
//LinkedList
LinkedList numbers = new LinkedList();
numbers.add(10);
numbers.add(20);
numbers.add(30);
numbers.add(40);
numbers.add(50);
numbers.remove(3);
System.out.println(numbers);

※ Java 컬렉션

List 컬렉션은 객체를 일렬로 늘어놓은 구조를 가지고 있다. 객체를 인덱스로 관리하기 때문에 객체를 저장하면 자동 인덱스가 부여되고 인덱스로 객체를 검색, 삭제 할 수 있는 기능을 제공한다. List 컬렉션은 객체 자체를 저장하는 것이 아니라 객체의 번지를 참조한다.

동일한 객체를 중복 저장 할 수 있는데, 이 경우 동일한 번지가 참조된다. null도 저장이 가능한데, 이 경우 해당 인덱스는 객체를 참조하지 않는다

ArrayList vs LinkedList

	추가/삭제	인덱스 조회
ArrayList	느림	빠름
LinkedList	빠름	느림