[자료구조] 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)