본문 바로가기

CS/자료구조

[자료구조] List

2021년 12월 29일에 작성된 글입니다.

📋 List

순서를 가진 요소들의 모임

Array vs List

  Array List
물리적 순서와 논리적 순서 일치 일치하지 않아도 됨
크기 고정 가변
메모리 할당 정적 동적

List의 연산

  • add
    새로운 요소를 리스트의 끝, 처음, 중간에 추가한다.
  • remove
    기존의 요소를 리스트의 임의의 위치에서 삭제한다.
  • clear
  • 모든* 요소를 삭제한다.
  • replace
    기존의 요소를 대치한다.
  • contains
    리스트가 특정한 요소를 가지고 있는지 확인한다.
  • get
    리스트의 특정 위치의 요소를 반환한다.
  • size
    리스트 안의 요소의 개수를 센다.
  • isEmpty
    리스트가 비었는지 확인한다.

ArrayList

= Dynamic Array

0 1 2 3 4 5 6 7 8 9
A B C D E          

1차원 배열에 요소들을 순서대로 저장

  • 구현이 간단
  • 삽입, 삭제 시 오버헤드

ArrayList의 연산

  • add
    삽입 위치 다음에 요소가 있을 경우 다음 요소들을 이동(shift)해줘야 한다. O(n)
  • remove
    삭제 위치 다음에 요소가 있을 경우 다음 요소들을 이동(shift)해줘야 한다. O(n)
  • get
    배열의 인덱스를 이용해 해당 요소에 접근할 수 있다. O(1)

LinkedList

A → B → C → D → E

노드(node)에 요소와 다음 노드의 주소를 저장

  • 구현이 복잡
  • 삽입, 삭제가 효율적

LinkedList의 연산

  • add
    새로운 노드를 생성하고 이전 노드가 새로운 노드를 가리키도록 한다. O(1) ~ O(n)
  • remove
    이전 노드가 삭제하려는 노드의 다음 노드를 가리키도록 한다. O(1) ~ O(n)
  • get
    처음부터 순차적으로 접근한다. O(n)

'CS > 자료구조' 카테고리의 다른 글

[자료구조] Heap  (0) 2024.09.04
[자료구조] Priority Queue  (0) 2024.09.04
[자료구조] Tree  (0) 2024.09.04
[자료구조] Queue  (0) 2024.09.04
[자료구조] Stack  (0) 2024.09.04