연결 리스트 2-1

연결 리스트 

 

 

지난 포스팅에 이어 연결 리스트에 관해 알아보려 한다.

우선 메모리 할당에 관해 알아보자.

 

메모리의 동적 할당 

 

malloc() 함수 : 메모리를 동적으로 할당하여 반환 

free() 함수 : 동적으로 받은 메모리 공간을 해제 

 

 

연결 리스트 

 

앞서 말했듯이 배열은 길이가 초기에 정해져 있어야 한다. 이러한 단점을 보완하기 위해 연결 리스트를 사용한다. 

연결 리스트는 동적 할당된 메모리들을 순차적으로 연결하는 것이다. 

따라서 첫 (메모리) 노드 head 부분의 주소값만 알고 있다면, 메모리들은 순차적으로 연결되어 있기에 나머지의 주소값을 몰라도 접근이 가능하다. 

 

1. 연결을 어떻게 시키는지 
2. 순차접근을 어떻게 하는지

에 관해 공부하는 것이다. 

 

 

구조체 정의 

typedef struct _node{
	int data;
    struct _node * next;
}
Node;

 

각각의 메모리 공간은 node, 구조체 변수라고 하며 포인터 변수를 사용해서 주소값을 저장하여 연결한다. 

 

- 노드 추가 

 

- 노드 조회 

순차적으로 조회  

 

- 노드 삭제 

포인터 변수 2개 필요

삭제할 노드와 삭제할 노드 그다음 노드를 가리킨 상태에서 한 칸씩 이동하며 노드를 삭제

 

 

구조체 노드의 추가 방법 

while(1) {
	newNode=(Node *)malloc(sizeof(Node));
    newNode->data = readData;
    newNode->next = NULL;
    
    if(head==NULL)
    	head = newNode;
    else
    	tail->next = newNode;
        
    tail = newNode;
}