Array & ArrayList & LinkedList

Array & ArrayList & LinkedList 의 특징

Array(배열)

• Array는 선언함과 동시에 크기를 함께 적어줘야하는 자료구조이다.
• Array를 선언하면서 특정 자료형과 배열의 크기를 함께 적어주면 특정 자료형이 들어갈 메모리공간을 미리 할당한다.
• 데이터를 삭제해도 공간이 남아있다.
• 장점
  • 미리 주소값(Index)을 할당하다보니 데이터검색이 빠르다.
• 단점
  • 선언한 크기 이상의 데이터를 가지는것은 불가능하기 때문에 데이터가 늘어나거나 하는 최대사이즈를 알수없는 상황에서 사용하기 부적합하다.
• ex) c, c++의 배열

ArrayList

• ArrayList는 크기가 정해져 있지 않다.
• 데이터에 순서가 Index형식으로 존재한다.
• 데이터를 중간에 추가하면 기존에 데이터는 Index의 변화가 일어난다. (뒤로 하나씩 밀리거나 당겨지거나)
• 장점
  • 배열과 같이 Index가 존재하기 때문에 데이터검색이 빠르다.
  • 데이터 검색에 $O(1)$의 시간복잡도
• 단점
  • 중간에 추가하면 기존 데이터의 Index에 변화가 일어나기 때문에 추가적인 연산이 필요하다.
  • 데이터 추가와 삭제에 $O(n)$의 시간복잡도

LinkedList

• 각 노드가 데이터와 포인터를 가지고 연결되어 있는 방식으로 데이터를 저장
• 한방향으로만 연결되거나, 양방향으로 연결, 순환구조로 연결 등의 여러가지 방식이 존재한다.
• 장점
  • 노드의 연결만 끊어주면 되기때문에 데이터의 추가 삭제가 간단함
  • 시간복잡도 $O(1)$
• 단점
  • 특정위치의 데이터를 알기 위해서 처음부터 탐색을 해야하기 때문에 시간이 소요됨
  • 시간복잡도 $O(n)$
• 추가 정보