연결 리스트

배열은 선형적인 자료구조이며, 메모리에 순차적으로 잡힌다. 

int a, int b, int c 이렇게 선언을 할 경우 메모리에 순차적으로 잡힐 수도 있지만, 안 잡힐 수도 있다.

반대로 배열 선언을 하여 배열 변수를 생성할 경우에는 메모리에 무조건 순차적으로 잡힌다.

배열의 선언과 사용법은 간단하나 배열은 단점이 있는 자료구조이기도 하는데,

예를 들어 0x00번지부터 0x0C번지까지 잡힌 int형 3개짜리 배열에서 가운데 값을 삭제를 하면

그 뒷번지 값을 끌어오는 연산에 부담이 생긴다.

(3개짜리가 아니라, 1000개라 생각해보라. 가운데 400번째 값을 삭제하면 599개의 값을 순차적으로 끌어오는 것이다.)

여기서 약 599번의 연산이 반복되며 퍼포먼스가 떨어진다.

배열은 논리적일 뿐만 아니라 물리적으로 메모리에 잡히는 반면에, 논리적인 형태로만 일렬로 잡히는 자료구조가 있다.

이 자료구조가 '리스트'다.

리스트는 보통 데이터 값+ 다음 리스트의 포인터 주소로 이루어진다. (자신의 전 노드를 가리킬 수도 있는 양방향 연결 리스트도 존재한다.)

리스트의 장점은 배열과 달리 중간 값이 삭제되도 앞의 노드와 뒤의 노드가 중간 노드의 포인터 주소를 삭제하고 바로 뒤의 노드만

연결해도 논리적으로 배열처럼 사용이 가능하다.