[Data Structure]연결 리스트 : 도입

배열에서는 각 인덱스의 값이 메모리 상에서 연이어 저장 되어 있다.

하지만 꼭 그럴필요가 있을까?

각 값이 메모리상의 여러군데 퍼져 있다고 해도  메모리 주소만 기억하고 있다면 

여전히 값을 연이어서 읽어들일 수 있을것이다.

 

이를 '연결 리스트' 라고 한다.

 

 

위의 그림과 같이 크기가 3인 연결 리스트는 각 인덱스의 메모리 주소에서 

자신의 값과 함께 바로 다음값의 주소 (포인터)를 저장한다.

3은 다음값이 없기에 NULL을 다음 값의 주소로 저장한다.

 

연결 리스트를 사용하기 위해서는 

아래 코드와 같이 간단한 구조체로 정의할 수 있다.

 

//typedef struct 대신에 typedef stuct node 라고 'node'를 함께 명시해 주는 것은,
//구조체 안에서 node를 사용하기 위함이다.

typedef struct node
{
	int number; //값
    struct node *next; //다음 노드를 가리키는 포인터 
}

 

 

배열과 비교했을때 굳이 메모리 공간을 확보하여 복사하지 않아도,

각각의 메모리들을 연결만 시켜줄 수 있으니 

메모리를 좀더 효율적으로 사용할수 있을것 같다는 생각이 든다.