[Data Structure] 리스트 (List)

1. 리스트

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

	선형	연결
구현	배열	포인터
메모리 저장	선언시 필요한 메모리 크기만큼 할당한다. 할당된 메모리의 시작 위치 부터 빈자리 없이 연속해서 저장한다.	노드 단위를 갖는데, 이 단위로 메모리를 할당한다. 저장 위치를 상관하지 않고 노드의 필드에 노드가 가르키는 다음 노드의 주소를 기록한다.
삽입/삭제 연산	연산 후에도 자료가 빈자리 없이 순서대로 저장된다. 이때 자료의 물리적 순서와 논리적 순서가 일치한다.	연산 후에 논리적 순서가 변경되더라도 물리적 위치는 변하지 않는다. 이때 노드의 필드 정보만 변한다.

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

 

 

2. 노드 (Node)

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

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

이런식으로 노드끼리 연결되어있습니다.

---

이것이 리스트에 대한 간략한 소개입니다. 자세한 것은 다음 포스트부터 본격적으로 다뤄보도록 하겠습니다.