리스트(List) 란?

자료구조의 인터페이스

 

Iterable 함수

• hasNext

List 란

• ArrayList, LinkedList 의 구현체이다. 물론 Vector, Stack은 지금은 사용하지않고 호환성을 위해 남아있는 Class 이다.
• 리스트는 순서가 있는 엘리먼트의 모임으로 배열과는 다르게 빈 엘리먼트는 절대 허용하지 않는다.
• 리스트는 배열이 가지고 있는 인덱스라는 장점을 버리고 대신 빈틈없는 데이터의 적재 라는 장점을 취함
• 리스트에서 인덱스는 몇 번째 데이터인가 정도(순서)의 의미를 가진다. (배열-Array에서의 인덱스는 값에 대한 유일무이한 식별자)
• 빈 엘리먼트는 허용하지 않는다. => java에서는 허용하는 경우가 있음
• 순차성을 보장하지 못하기 때문에 spacial locality 보장이 되지 않아서 cash hit가 어렵다.(데이터 갯수가 확실하게 정해져 있고, 자주 사용된다면 array가 더 효율적이다.)
• 불연속적으로 메모리 공간을 차지.
• 포인터를 통한 접근

List의 장점

• 포인터를 통하여 다음 데이터의 위치를 가르켜고 있어 삽입 삭제의 용이.
• 동적이므로 크기가 정해져 있지 않다.
• 메모리의 재사용 편리
• 불연속적이므로 메모리 관리의 편리

단점

• 검색 성능이 좋지 않다.
• 포인터를 통해 다음 데이터를 가르키므로 추가적인 메모리 공간 발생.

추가/삭제 조회

Array	느림	빠름
List	빠름	느림

• 배열 : 데이터의 크기가 정해져 있고, 추가적인 삽입 삭제가 일어 나지 않으며 검색을 필요로 할 때 유리.
• 리스트 : 데이터의 크기가 정해져 있지 않고, 삽입 삭제가 많이 일어나며, 검색이 적은 경우 유리.

ArrayList 란

일반 배열과 ArrayList는 인덱스로 객체를 관리한다는 점에서 동일하지만, 크기를 동적으로 늘릴 수 있다는 점에서 차이점이 있다.ArrayList는 내부에서 처음 설정한 저장 용량(capacity)가 있다. 설정한 저장 용량 크기를 넘어서 더 많은 객체가 들어오게 되면, 배열 크기를 1.5배로 증가시킴(더블링)

• 장점
  • ArrayList와 Vector 같이 배열을 이용한 자료구조는 데이터를 읽어오고 저장할 때는 효율적
• 단점
  • 데이터의 추가 삭제에 비교적 메모리가 많이 소모된다.(한칸씩 당겨주거나 밀어줘야함, 더블링)

LinkedList 란

arrayList의 단점인 데이터의 삽입 삭제의 시간복잡도 O(n) 의 단점을 보완하기 위해 만들어진 데이터구조이다.

메모리공간에 연속적으로 할당되지는 않는다.

• 장점
  • 데이터를 추가삭제할때 공간을 늘려주거나 축소할 필요없이 노드의 next prev 값만 변경해주면 되기때문에 추가삭제에 용이하다
• 단점
  • 처음노드나 마지막노드의 next, prev 값을 따라가서 찾아야 하기때문에 특정 원소에 위치에 접근할때는 시간복잡도가 O(n) 이다.
  • 위와 같은 이유로 수정에 대한 시간복잡도도 O(n) 이다

 

Array vs ArrayList vs LinkedList 비교