Array vs LinkedList

Array란?

 

특징

• 데이터들이 순서대로 쭉 나열되어있는 형태
• index가 존재함

조회

• 각 데이터의 index를 가지고 있고 무작위 접근이 가능하기 때문에,
  index로 각 데이터에 직접 접근이 가능

데이터 삽입과 삭제

• 데이터의 삽입과 삭제 시 그만큼 index를 맞춰주어야 함
• 예시 : 5개의 데이터가 있을 때 맨 앞을 삭제했다면 뒤쪽의 나머지 4개는 앞으로
  한 칸씩 이동해야됨
• 이로 인해 삽입과 삭제가 많다면 Array는 비효율적임

LinkedList

특징

• 각 데이터들 앞, 뒤 데이터의 주소값을 가지고 있음
• index가 존재하지 않음

조회

• 순차적 접근이기 때문에 조회의 속도가 느리다

데이터 삽입과 삭제

• 데이터의 삽입과 삭제 시 앞, 뒤의 데이터에 주소값만 변경해주면됨
• 예시 : 5개의 데이터가 있을 때 두 번째 데이터를 삭제 했다면 1번 데이터에 3번의 주소값을
  주고 3번 데이터에 1번 데이터의 주소값을 넣어주면된다
• 이로 인해 삽입과 삭제가 많다면 Array에 비해 효율적임

Array vs LinkedList

• 소량의 데이터를 바탕으로 측정하면 큰 차이는 없다
• 위의 퍼포먼스 테스트처럼 조회 시에는 Array가 우위에 있고
• 삽입/삭제 시에는 LinkedList가 우위에 있다 (특히 삭제)
  1. 삽입/삭제 시에 처음 혹은 마지막부터 순차적으로 데이터를 삭제한다고 하면
  Array도 충분히 빠르다
  2. 하지만 중간부터(비순차적)으로 삽입/삭제하는 경우에는 LinkedList가 빠르다