ArrayList/LinkedList

LinkedList(Collecion<> c)
: 두번째 오버로딩 생성자를 이용하며 arrayList는 Collection이라고 불릴 수 있으므로, 기존 arrayList를 LinkedList로 만든다.

ArrayList를 생성 후 LinkedList로 담을 수 있다.

ArrayList<Integer> arrayList=new ArrayList<Integer>();

arrayList.add(3);
arrayList.add(7);
arrayList.add(5);

LinkedList<Integer> intList =new LinkedList<Integer>(arrayList);

👀 LinkedList와 ArrayList의 비교

• get(4)와 같은 구현은 ArrayList가 더 효율적
  • ArrayList는 index를 바로 참조
  • LinkedList는 0번째 요소부터 4번째까지의 요소를 참조를 통해 계속 확인
• set(2,4)와 같은 구현은 LinkedList와 ArrayList 모두 같은 결과값을 반환하지만, 구현은 ArrayList가 더 효율적
  • ArrayList는 2라는 index를 바로 참조
  • LinkedList는 0번째 요소부터 2까지의 요소를 참조를 통해 계속 확인
• remove()는 LinkedList가 더 효율적
  • LiskedList의 경우 index의 값을 찾는데 시간이 소요되지만 지워야 할 위치를 찾은 뒤, 삭제하고 참조를 통해 앞 뒤를 다시 연결해 효율적
  • ArrayList는 값을 지운 뒤, 그 index 뒤의 요소들을 shift 해야 하는 비용이 생김
• ListIterator()는 ArrayList가 더 효율적

LinkedList?

• 객체 Node간 연결을 이용한 설계 (Doubly Linked List)
• 참조 기반으로 인덱스를 지원하나 상수 시간이 소요 되지 않음
  • LinkedList는 노드들이 링크로 연결됨
• 특정 index를 가지고 있기 않기 때문에, 특정 위치에 넣으려면 그 index값을 찾아야 함
• 특정 위치를 찾는데 비용이 소모되지만, ArrayList와 다르게 요소들을 뒤로 밀 필요가 없어 시간이 더 빠름

Array의 sort는 삽입정렬과 합병정렬이 적절하게 합쳐진 TimSort를 이용