[Data Structure] 리스트 (List)

✔ 리스트

리스트(List)란?

• 값과 포인터를 묶은 노드라는 것을 포인터로 연결한 자료구조
• 트리 구조의 근간이 되는 자료구조

리스트의 특징

1. 인덱스가 없어 값에 접근하려면 Head 포인터부터 순서대로 접근해야 하므로 속도가 느림
   • 논리적 저장 순서와 물리적 저장 순서가 일치하지 않음
   • 원하는 위치를 Search 하기 위해 첫 번째 원소부터 다 확인하며 순회
   • O(N)의 시간 복잡도로 해당 원소에 접근
2. 포인터로 연결되어 있으므로 데이터를 삽입하거나 삭제하는 연산 속도가 빠름
   • 각각의 원소들은 자기 자신 다음에 어떤 원소인지만을 기억하므로 이 부분만 다른 값으로 바꿔 삭제와 삽입이 가능
   • O(1)의 시간 복잡도로 삽입, 삭제 가능
3. 선언할 때 크기를 별도로 지정하지 않아도 됨
   • 추가할 때마다 동적으로 메모리 할당을 받게 됨
   • 메모리는 새로운 노드가 추가될 때 런타임에 할당됨
4. 포인터를 저장할 공간이 필요하므로 배열보다 구조가 복잡함

리스트를 언제 사용할까?

• 크기가 변하는 데이터를 다루며, 데이터의 삽입과 삭제가 많을 때 유리

연결 리스트(LinkedList)란?

1. 리스트를 사용하여 데이터를 관리
2. 리스트와 동일한 특징을 가짐

Array vs ArrayList vs LinkedList

• 데이터에 접근하는 것이 빈번하게 일어난다면 Array (ArrayList)
• 삽입과 삭제가 빈번하게 일어난다면 LinkedList 사용