Java - LinkedList

iseon_u·2022년 5월 22일
0

Java

목록 보기
53/75
post-thumbnail

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 (연결 기반)느리다빠르다데이터가 많을수록 접근성 떨어진다.
profile
🧑🏻‍💻 Hello World!

0개의 댓글