링크드 리스트는 메모리상에서 크기를 정해서 일렬로 입력되는 배열과는 다르게
자료의 논리적인 순서와 메모리 상의 물리적인 순서가 일치하지 않고, 개별적으로 위치하고 있는 원소의 주소를 연결하여
하나의 전체적인 자료구조를 이룬다.
즉, 논리적인 순서로는 첫번째에 있는 원소라도 메모리상에서는 가장 끝에 위치해 있을 수 있다는 것이다.
이를 가능하게 하는 것이 링크이다.
링크를 통해 원소에 접근하므로, 순차 리스트에서처럼 물리적인 순서를 맞추기 위한 작업이 필요하지 않다.
이는 곧 자료구조의 크기를 동적으로 조정할 수 있다는 것을 의미하고,
이를 통해 메모리의 효율적인 사용이 가능하게 된다.
오른쪽과 같은 논리적 순서라도 왼쪽과 같이 저장될 수 있다는 것이다.
링크드 리스트를 구성하는 것으로는 다음과 같이 설명할 수 있다.
- 노드
노드는 링크드 리스트에서 하나의 원소에 필요한 데이터를 갖고 있는 자료 단위로,
값을 저장하는 데이터 필드와 다음 노드의 주소를 저장하는 링크 필드를 가진다.
- 헤드
링크드 리스트의 처음 노드를 가리키는 레퍼런스이다
이런 식으로 구성되어 있다고 생각해보자.
HEADER는 값을 가지지 않고 해당 링크드 리스트의 가장 첫번째 노드를 가리키고,
첫번째 노드부터 차례대로 다음 노드를 가리키고 있는 구조이다.
LINK를 통해 물리적으로 인접하지 않은 노드로 이동이 가능하게 되고,
NODE에 들어있는 DATA 필드를 통해 필요한 값을 저장 및 추출할 수 있는 것이다.
라고 이해했다.