LinkedList

0

Collection

목록 보기
3/11

LinkedList를 알아보기 전에

먼저 배열의 장단점을 알아보자

장점 : 배열은 구조가 간단하고 데이터를 읽는데 걸리는
시간(접근시간, access time)이 짧다.

단점 1 : 크기를 변경하기가 어렵다.

  • 크기를 변경해야 하는 경우 새로운 배열을 생성 후 데이터를 복사해야함.
  1. 더 큰 배열 생성 2. 복사 3. 참조변경
  • 크기변경을 피하기 위해 충분히 큰 배열을 생성하면 메모리가 낭비됨.

단점 2 : 비순차적인 데이터의 추가, 삭제에 시간이 많이 걸린다.

  • 데이터를 추가하거나 삭제하기 위해, 다른 데이터를 옮겨야 함.
  • 그러나 순차적인 데이터 추가(끝에 추가)와 삭제(끝부터 삭제)는 빠르다.

LinkedList는 배열의 단점을 보완

  • 배열과 달리 링크드 리스트는 불연속적으로 존재하는 데이터를 연결(link)한다.

array는 각 요소가 연속적(객체의 주소가 0x100, 0x104 와 같이 4byte 차이) 그러나 LinkedList는 각 요소가 어디에 있는지 알 수가 없다. (0x200 이후에 0x300, 0x350 과 같이 불연속적이다)

LinkedList 형태의 데이터는 각 하나하나의 객체를 노드라고 하며 객체의 구성요소는

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

하나의 개별 요소들을 연결해 놓기 때문에 변경에 유리하다.

데이터의 삭제 : 단 한 번의 참조변경만으로 가능,
객체에 포함된 다음 노드의 주소를 변경만하면 된다. 그 이후 지워진 주소는 Garbage Collector 에 의해 삭제됨

데이터의 추가 : 한번의 Node객체생성과 두 번의 참조변경만으로 가능

배열의 단점을 보완하여 사용하기 위해 만든 것이 LinkedList이다.

LinkedList의 단점

단점 : 링크드 리스트 - 연결리스트, 데이터 접근성이 나쁨
데이터가 불연속적이기 때문에 이동이 많다.
(징검다리처럼 하나하나 넘어가야한다.)

더블리 링크드 리스트(Doubly Linked List) - 이중 연결리스트, 접근성 향상
class Node {
Node next; // 다음 요소
Node Previous; // 이전 요소
Object obj;
}
앞뒤의 이동이 가능해졌지만 한번에 여러개를 이동 할 수는 없다.

더블리 써큘러 링크드 리스트(Doubly Circular Linked List) - 이중 원형 연결리스트

  • 더블리 링크드 리스트와 같은 구조이나 인덱스 맨 앞, 뒤에 주소를 연결하여 사용

ArrayList vs LinkedList - 성능 비교

순차적으로 추가/삭제하기 - ArrayList 승
// 큰 차이는 없다, 약 2배~4배차이
// 순서대로 추가하고 삭제하기 때문에 데이터의 이동이 없기때문

비순차적으로 데이터를 추가/삭제 - LinkedList가 빠름
// 약 20배 정도의 차이

접근시간(access time) - ArrayList 승
// 압도적으로 빠름

Collection읽기(접근시간)추가/삭제 비교
ArrayList빠르다느리다, 순차적인 추가 삭제는 더 빠름
비효율적인 메모리 사용 -> 성능을 높이고자 배열을 크게 잡아야 하기 때문
LinkedList느리다빠르다
데이터가 많을수록 접근성이 떨어짐

0개의 댓글