[자료구조] 리스트 (ArrayList vs LinkedList)

1. 리스트 1.1 리스트란? 리스트(List)란 앞에서 공부한 배열, 스택, 큐 등과 같은 선형 자료구조이다. 그렇다면 이들과 리스트의 차이점은 무엇일까? 스택과 큐의 경우 자료의 접근이 전단(front) 혹은 후단(rear)에 제한되어 있다. 하지만 리스트는 이러한 제한이 없다. 즉, 임의의 위치에 있는 항목에 접근이나 연산이 가능하다는 것이다. 1.2 배열 vs 리스트 배열(array) 또한 임의의 위치에 접근이 가능하다. 그렇다면 배열과 리스트의 차이는 무엇일까? 배열은 각각의 원소에 순서대로 index가 할당되어 있다. 위 배열에서 c 원소를 삭제하는 경우 아래와 같은 형태가 된다. 삭제한 c의 메모리 공간은 빈 공간으로 남아있으며, d와 e의 index는 변함이 없다. 만약 위의 행위가 리스트..