LinkedList
-
일반적인 리스트로 불리며, 노드로 연결된 데이터를 저장하는 자료구조
-
데이터의 순서를 유지할 수 없지만, 데이터를 추가하거나 삭제하기 쉬움
-
배열과 달리 배열의 크기를 우리가 지정하거나 변경할 필요 없음
-
배열처럼 데이터를 순서대로 표현하는 자료구조
-
연속적인 메모리 위치에 저장되지 않는 선형 데이터 구조(포인터로 연결)
-
arrayList의 단점인 데이터의 삽입 삭제의 시간복잡도 O(n) 의 단점을 보완하기 위해 만들어진 데이터구조
장단점
장점
-
같은 타입의 동적 데이터 관리
- 크기가 정해져 있지 않음
-
삽입/삭제 용이
- 데이터를 추가삭제할때 공간을 늘려주거나 축소할 필요없이 노드의 next prev 값만 변경해주면 되기때문에
-
리스트 내에서 자료의 이동이 필요하지 않음
-
사용 후 기억 장소의 재사용 가능
-
연속적인 기억 장소의 할당이 필요하지 않음
단점
-
임의의 k번째 데이터에 대한 접근을 할 수 없음
- 즉, 첫 번째 노드부터 순차적으로 요소에 액세스(이진 탐색 불가)
-
포인터 메모리 공간이 각 노드에 필요
-
검색 성능이 좋지 않음
- 특정 자료의 탐색 시간이 많이 소요
-
포인터를 통해 다음 데이터를 가르키므로 추가적인 메모리 공간 발생
-
알고리즘이 복잡함
-
처음노드나 마지막노드의 next, prev 값을 따라가서 찾아야 하기때문에 특정 원소에 위치에 접근할때는 시간복잡도가 O(n)
-
위와 같은 이유로 수정에 대한 시간복잡도도 O(n)
시간 복잡도
Create 시간복잡도
- 리스트의 중간에 데이터를 넣을 경우 : O(N)
- 맨 앞이나 맨 뒤에 넣을 경우 : O(1) - 일반적으로 이 경우가 많음
Read/Update 시간복잡도- 맨앞이나 맨 뒤의 데이터를 확인하거나 바꿀 경우 : O(1)
- 중간의 데이터를 확인하거나 바꿀 경우 : O(N) - 일반적으로 이 경우가 많음
Delete 시간복잡도- 중간의 데이터를 삭제할 경우 : O(N)
- 맨앞이나 맨 뒤에 데이터를 확인하거나 바꿀 경우 : O(1) - 일반적으로 이 경우가 많음
배열은 언제 사용하고 리스트는 언제 사용할까?
-
리스트
- 일반적으로 데이터의 추가, 삭제가 많은 경우 리스트를 사용하는 것이 효율이 좋음
-
배열
- 데이터가 자주 추가, 삭제 되지 않고, 읽고 수정하는 경우가 많을 때 배열을 사용하는 것이 효율이 좋음
ArrayList
-
LinkedList와 차별적으로 배열과 유사한 형태로 List 컬렉션을 관리하는 자료구조
-
일반 배열과 ArrayList는 인덱스로 객체를 관리한다는 점에서 동일하지만, 크기를 동적으로 늘릴 수 있다는 점에서 차이점 존재
- 저장되며, 배열에 더 이상 저장할 공간이 없으면 보다 큰 새로운 배열을 생성해서 기존의 배열에 저장된 내용을 새로운 배열로 복사한 다음에 저장
-
ArrayList는 내부에서 처음 설정한 저장 용량(capacity) 존재
-
설정한 저장 용량 크기를 넘어서 더 많은 객체가 들어오게 되면, 배열 크기를 1.5배로 증가시킴(더블링)
장단점
장점
-
같은 타입의 데이터 수가 동적으로 변화하면서, 특정 K번째 위치의 데이터 조회가 빈번한 경우 빠르게 탐색 가능(이분탐색 사용 가능)
-
List 컬렉션(데이터군)을 배열과 같이 index를 통해 빠르게 접근 가능
-
포인터를 위한 메모리 사용 X
-
ArrayList와 Vector 같이 배열을 이용한 자료구조는 데이터를 읽어오고 저장할 때는 효율적
단점
-
크기가 한정되어 있기 때문에 삽입/삭제에 상당한 연산 수행
- 데이터의 추가 삭제에 비교적 메모리가 많이 소모(한칸씩 당겨주거나 밀어줘야함, 더블링)
