리스트와 배열의 차이, 리스트 인터페이스

배열 : 동일한 타입의 원소를 선형적으로 관리하는 정적 데이터 구조

 

get - O(1)

add 맨뒤에 추가 - O(1)

insert 중간에 추가 - 넣으려는 인덱스부터 한칸씩 밀고 추가, o (N)

remove - 삭제한 후 삭제한 인덱스 뒤를 한칸씩 당겨주느라 o (N)

 

List - 동일한 타입의 원소를 선형적으로 관리하는 동적 데이터 구조

크기 가변적, List 인터페이스 구현체에 따라 특성이 다르다

 

구현체 3개

ArrayList - 인덱스를 통한 원소 접근 빠름, 삽입/삭제 느림

LinkedList - 헤드부터 하나씩 타고 이동하기에 인덱스를 통한 접근 느림, 삽입 삭제는

한 노드에서 자르고 포인터만 이어주면 되서 빠르다

Vector - ArrayList와 비슷하고 thread - safe 해서 멀티 쓰레드 환경에서 안전하게 사용 가능하지만 느림

실제 환경에서는 ArrayList나 LinkedList를 사용해서 구현한 자료구조에 여러 사용자가 접근해서 수정/삭제를 하면

문제가 생기기에 동기화해서 사용해야한다

 

• List 인터페이스

list.java 파일에 가서 볼 수 있다

리스트 인터페이스를 순서가 있는 컬렉션, 인덱스를 통한 접근이 가능하고, ListIterator를 제공한다