리스트 & 연결 리스트

리스트(List)

• 값을 저장하는 ADT(Abstract Data Type: 추상 자료형)
• 순서가 있음
• 중복을 허용

List 구현체

• Array List
• Linked List

Array List

• 배열(Array)을 사용하여 List를 구현
• 메모리에 연속적으로 값이 할당됨

Linked List

• 노드를 연결시키는 형태로 구현
• 메모리에 연속적으로 값이 할당되지 않고, 다음 노드의 위치를 가리키는 주소값이 존재
• 리스트의 처음과 끝을 가리키는 head, tail이 존재함(둘 중 하나만 존재할 수도 있음)

Linked List의 여러 종류들

• circular linked list
  

  head와 tail이 연결되어 있는 형태(순환 구조를 가짐)

• doubly linked list
  

  기존의 단방향성 리스트에서 양방향성 리스트로 발전됨(원하는 위치로 조금 더 빠른 이동이 가능)

• circular doubly linked list
  

  위 두가지의 list 특성을 모두 가짐

Array List와 Linked List의 차이점

	ArrayList	LinkedList
구현	배열(Array) 사용	노드를 연결(linked)
데이터 접근 시간	모든 데이터 상수 시간 접근	위치에 따라 이동 시간 발생
삽입/삭제 시간	삽입/삭제 시 데이터 시프트가 필요한 경우 추가 시간 발생	삽입/삭제 위치에 따라 그 위치까지 이동하는 시간 발생
리스트 크기 확장	배열 확장이 필요한 경우 새로운 배열에 복사하는 추가 시간 발생	-
검색	최악의 경우 리스트에 있는 아이템 수 만큼 확인	최악의 경우 리스트에 있는 아이템 수 만큼 확인
Java 구현 예	ArrayList	LinkedList

Java에서 ArrayList, LinkedList 둘 중 어떤것을 써야할까?

ArrayList, LinkedList 모두 오늘날에는 점차 개선이 되면서 성능면에서 차이가 거의 없어졌다고 한다.

추가로, Java의 LinkedList를 구현한 개발자인 Josh Bloch의 트위터의 트윗을 인용해왔다..

정작 구현 당사자도 LinkedList를 한번도 써본적이 없다니...
나도 ArrayList나 써야지~~