리스트 List

리스트는 자료(데이터)를 순서대로 나열한 자료구조 입니다. 순서대로 나열되어있다는 점 때문에 순차 자료구조라고 부르기도 합니다. 리스트에는 선형 리스트와 연결 리스트 두 가지가 존재합니다. 두 가지는 순서대로 자료가 나열되어있다는 점은 같지만 다음과 같은 차이점이 있습니다.

• 선형 리스트: 물리적 주소 == 논리적 주소
• 연결 리스트: 물리적 주소 != 논리적 주소

노드 Node

위에서 갑자기 노드라는 용어가 등장했습니다. 이 단어는 리스트에서, 이후에도 쭉 나오는 개념이니 이해하고 넘어가시면 좋습니다. 노드란 리스트의 자료(데이터)를 의미합니다. 노드를 요소라고 하기도 합니다. 이 포스트 시리즈에서는 노드라는 용어를 사용하도록 하겠습니다.

노드는 자료를 가지고 있는 데이터 필드와 다음 노드를 가리키는 포인터를 저장하고 있는 링크 필드로 구성되어 있습니다.
이렇게 노드끼리 링크 필드를 통해 연결되어있습니다.