Java 자료구조 List (1) 간략히 보기

List 란?

• 자료구조
  • 선형적인 자료구조
  • 데이터를 일렬로 늘여 놓은 형태
  • 데이터간에 순서가 존재함

• 연산

  • 데이터 삽입하기
  • 데이터 삭제하기
  • 데이터 탐색하기

• 종류

  • ArrayList
  • LinkedList
    • Single Linked List
    • Double Linked List

ArrayLIst

• 배열 기반의 리스트 -> 인덱스가 존재함
• 메모리 공간을 연속적으로 사용
• 컴퓨터에서 접근하는 속도가 빠름
• 고정된 공간을 할당 받음
• 중간에 데이터를 삽입할 경우 데이터를 옮겨줘야함
  • 예 1,2,3,4,5 가 있고 인덱스 2번에 5를 넣을 경우
  • “3” 이 “5로”바뀌므로 3,4,5를 뒤로 옮겨줘야함
  • 삭제도 마찬가지 (뒤에 있는 데이터를 앞으로 옮겨줘야함)
  • 시간복잡도는 O(N)
  • 데이터 갯수에 상관없이 인덱스로 데이터를 가져오기 때문에 데이터를 갖고 오는 속도는 빠름

LinkedList

• 실제 컴퓨터 메모리상에서 물리적으로 연속적인 공간을 차지하고 있지 않음
• 데이터간의 이동자체에 속도가 더 걸림

LinkedList vs Array 비교

	LinkedList	ArrayList
추가	O(N)	O(1),O(N)
삽입	O(N)	O(N)
삭제	O(1)	O(N)
검색	O(N)	O(1)

• 객체 Node는 내부에 data와 next 변수를 갖고 있음
  • data는 노드의 값 next는 다음 노드를 가리키는 참조값이다.