[자료구조] 배열과 연결리스트

배열(Array)

• 배열은 선형 자료구조이면서 연속된 자료구조에 속한다.
• 연속된 자료구조는 모든 원소를 단일 청크에 저장한다.
  • 특정 원소에 접근할 때 주변의 인접한 메모리도 캐시로 가져온다. 다시 주변 원소에 접근할 때 빠른 동작이 가능하다. (캐시지역성)
  • 모든 원소를 첫번째부터 순차적으로 접근하는 경우, 다음 원소를 캐시에서 바로 참조할 수 있다.
• 원소들은 같은 자료형과 같은 크기의 메모리를 사용한다.

• 원소의 수에 상관없이 모든 원소에 바로 접근이 가능하다 = O(1)
  • 첫번째 원소의 메모리 주소가 Addr이면
  • 두번째 원소의 메모리 주소는 Addr + (자료형의 크기)
  • 세번째 원소의 메모리 주소는 Addr + (자료형의 크기) * 2
  • n번째 원소의 메모리 주소는 Addr + (자료형의 크기) * (n - 1)
• 배열 중간에 데이터를 추가하거나 삭제할 때, n번의 연산이 필요하다 = O(n)

배열 중간에 데이터 삽입

배열 중간의 데이터 제거

• 배열 마지막에 데이터를 추가하거나 삭제할 때, 1번의 연산만 필요하다 = O(1)

 

연결리스트(Linked List)

• 연결리스트는 여러 개의 노드(Node)에 데이터를 저장한다.

• 각 노드는 서로 다른 메모리 위치에 저장된다.
• 노드는 데이터(data)와 다음 노드의 메모리 주소를 가리키는 포인터(next)를 가지고 있다.
  • 마지막 노드의 next는 NULL이다.
• 특정 원소에 접근하려면 첫번째 노드부터 다음 노드에 순차적으로 접근해야 한다 = O(n)
• 리스트에 데이터를 추가하거나 삭제할 때 해당 노드의 포인터만 수정하면 된다 = O(1)

연결리스트 중간에 데이터 삽입

결론

	배열	연결리스트
임의접근	O(1)	O(n)
맨 뒤에 원소 삽입	O(1)	O(1)
중간에 원소 삽입	O(n)	O(1)
캐시 지역성	있음	없음