LinkedList

📚참고
컬렉션 프레임워크와 핵심 인터페이스

 

 

 

 

 

 

 

 

 

배열의 장단점

 

장점

• 구조가 간단하고 데이터를 읽는데 걸리는 시간(access time)이 짧다.
  • 배열은 연속적이기 때문에 요소의 주소값을 찾아내는게 빠르다.

 

 

단점

• 런타임 시, 크기를 변경할 수 없다.
• 크기를 변경해야 하는 경우, 새로운 배열을 생성 후 데이터를 복사해야한다.
  1. 1. 더 큰 배열 생성
  2. 2. 값 복사
  3. 3. 참조변수 값 변경
• 크기 변경을 피하기 위해 큰 배열을 생성하면 메모리가 낭비
  • 런타임 중 배열의 크기 변경은 불가하므로 배열길이를 잘 지정해줘야함 (보통 2배)
• 비순차적인 데이터의 추가/삭제에 시간이 많이 걸린다.
  • 데이터를 추가/삭제하기 위해, 다른 데이터를 옮겨야 한다.
  • 그러나 데이터를 순차적으로 끝에 추가, 끝부터 삭제하는 것은 빠르다.

 

 

 

 

 

 

 

 

 

LinkedList

 

• 배열의 단점을 보완
• 배열과 달리 불연속적으로 존재하는 데이터를 연결
• 데이터의 삭제
  • 단 한 번의 참조변경만으로 가능하다.

 

class Node {
    Node next;	// 다음노드
    Object obj;	// 데이터
}

 

• 데이터의 추가
  • [ 1번의 Node 객체 생성 + 2번의 참조변경 ] 만으로 가능

 

•  단점
  • 데이터 접근성이 나쁨
  • 배열은 연속적이여서 한번에 이동이 가능하나 링크드리스트는 데이터를 한번에 찾아가는 것이 안 된다.
  • 또한 링크드리스트의 노드는 뒷 요소의 참조값만 갖고 있기 때문에 앞 요소를 찾아가지 못한다.
  • 이를 보완하기 위한 컬렉션 클래스가 더블리 링크드 리스트(doubly linked list)

 

 

 

 

Doubly Linked List

 

• 이중 연결 리스트
• 링크드리스트의 단점을 보완
• 앞뒤 노드의 참조값을 가지고 있어 접근성이 향상
• 그러나 한번에 이동하는 것은 여전히 불가하고 앞뒤로 이동만 가능하다.

 

class Node {
    Node next;		// 다음노드
    Node previous;	// 이전노드
    Object obj;		// 데이터
}

 

 

 

 

 

Doubly Circular Linked List

 

• 이중 원형 연결 리스트
• 맨 앞 노드에는 맨 뒷 노드의 참조값을, 맨 뒷 노드에는 맨 앞 노드의 참조값을 저장한다.

 

 

 

 

 

 

 

 

 

 

ArrayList vs LinkedList 성능 비교

 

• 순차적으로 데이터 추가/삭제 : ArrayList가 빠름
• 비순차적으로 데이터 추가/삭제 : LinkedList가 빠름
• 접근시간 : ArrayList가 빠름
  • 인덱스가 n인 데이터의 주소 = 배열의 주소 + n * 데이터 타입의 크기

 

컬렉션	읽기 (접근시간)	데이터 추가/삭제	비고
ArrayList	빠르다.	느리다.	순차적인 추가/삭제는 빠름 비효율적인 메모리 사용
LinkedList	느리다.	빠르다.	데이터가 많을수록 접근성이 떨어짐 (한번에 이동이 불가)