자료 구조 기초 (Array, List, Linked List)

배열(Array)

• 연속적인 공간을 할당 받아 데이터를 저장한다.
• 원소에 접근할 때 index라는 유니크한 식별자를 사용하여 특정 원소에 빠르게 접근 할 수 있다.
• 중간에 있는 원소 삽입/삭제가 느리다. 왜냐하면 중간에 있는 원소를 건드릴 경우, 그 뒤에 있는 모든 원소의 위치를 변경하는 추가 작업이 필요하기 때문이다.

리스트(List)

• 리스트의 각 원소는 메모리 상 연속적인 공간에 할당되지 않을 수 있다. 리스트의 각 원소는 다음 원소를 가리키는 포인터 개념을 사용하여 각 원소의 순서를 구현한다.
• 그래서 배열보다 데이터 삽입/삭제가 빠르다. 앞, 뒤 원소의 포인터만 바꿔주면 되기 때문에!
• 그 대신 원소를 검색하기 위해서는 첫 번째 원소부터 선형 검색(Linear Search) 을 해야 한다.

연결 리스트(Linked List)

• 각 원소를 Node라고 하며, 각 노드는 데이터/다음 노드 를 가리키는 포인터 변수를 가지고 있다. 포인터를 위한 추가 메모리 공간도 필요하다.
• 링크드 리스트의 맨 앞 노드는 Head, 맨 끝 노드는 Tail이라고 한다.
• 각 노드의 앞 노드는 Predecessor Node(전임 노드), 뒤 노드는 Successor Node(후임 노드) 라고 한다.