LinkedList

---

배열 장점

• 배열은 구조가 간단하고 데이터 접근 시간 (access time) 이 짧다.
• 순차적 데이터 추가 (끝에서 추가) 와 삭제 (끝에서 삭제) 가 빠르다.

배열 단점

• 크기 변경 불가
  • 크기 변경할 경우 새로운 배열 생성 후 데이터 복사
  • 미리 큰 배열을 생성하면 메모리 낭비
• 비순차적인 데이터 추가, 삭제 시간이 많이 걸린다. (중간 지점 부터)
  • 추가, 삭제시 다른 데이터를 옮겨야 한다.

LinkedList - 배열의 단점을 보완

• 배열과 달리 LinkedList는 불연속적으로 존재하는 데이터를 연결 (link)
• 변경에 유리하다.
• 데이터 삭제는 단 한번의 참조 변경으로 가능
• 데이터 추가는 한번의 Node 객체 생성과 두 번의 참조 변경만으로 가능

class Node { // 노드
		Node next; // 다음 노드의 참조 변수
		Object obj; // 노드 데이터
}

LinkedList - 단점

• 연결 리스트, 데이터 접근성이 나쁘다.
• 노드는 다음 노드 위치만 알기 때문에 배열처럼 한번에 이동 불가
• 이전 노드도 알 수 없다.

Doubly linked list

• 이중 연결 리스트, 접근성 향상
• 앞 뒤로 이동 가능

class Node { // 노드
		Node next; // 다음 노드의 참조 변수
		Node previous; // 이전 노드의 참조 변수
		Object obj; // 노드 데이터
}

Doubly circular linked list

• 이중 원형 연결 리스트
• 이중 연결 리스트의 null 값에 처음과 끝을 연결

ArrayList vs. LinkedList 성능 비교

1. 순차적으로 데이터 추가 / 삭제 - ArrayList 빠름
2. 비순차적으로 데이터 추가 / 삭제 - LinkedList 빠름
3. 접근 시간 - ArrayList 빠름

컬렉션	읽기 (접근 시간)	추가 / 삭제	비고
ArrayList (배열 기반)	빠르다	느리다	순차적인 추가 / 삭제 빠름
비효율적 메모리 사용
LinkedList (연결 기반)	느리다	빠르다	데이터가 많을수록 접근성 떨어진다.