list/linked list

리스트는 배열과 혼동해서 많이 쓰인다. 배열과 구분되게 정확히 말하려면 링크드 리스트라고 말한다.

링크드 리스트는 각 인덱스에 value 영역, pointer 영역이 있다. value 영역은 말 그대로 필요한 값이고, pointer 영역은 다음 인덱스의 주소를 저장한다.

다음 인덱스의 주소를 아예 알고 있으므로 메모리에 물리적으로 붙어있을 필요가 없다.

붙어있지 않기 때문에, 조회에 시간이 O(n)이 걸린다.

붙어있지 않기 때문에, (값을 당기거나 밀 필요가 없으므로) 삽입과 삭제는 O(1) 이 걸린다.