연결리스트 정리

연결리스트(linked list)

각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 작성하는 자료구조.

 

typedef struct s_list
{
	void			*content;
	struct s_list	*next;
}	t_list;

 

나는 이렇게 노드를 작성했는데, 이렇게 한 구조체 안에 다음 노드의 주소가 들어있는 형식이라고 보면된다. 

 

연결리스트 의 처음 노드

가장 첫번째 노드를 가르킬 포인터가 항상 존재해야 한다. 

그래야 앞부분을 수정해도 리스트의 연결을 잊어버리지 않을 수 있기 때문이다.

보통은 이 첫번째 노드를 가르킬 포인터를 head라고 하는데, 

 

t_list* head;

void init()
{
    head = NULL;
}

이런식으로 초기화 하여 사용한다. 

연결리스트가 비어있는 것은 어떻게 확인 할 수 있을까? 

head == NULL

이면 비어있는것이다. 

 

연결리스트 의 연결

연결리스트의 연결은 크게 세가지로 나눌 수 있겠다. 

• 가장 앞의 노드를 삽입하는 경우
• 중간의 노드를 삽입하는 경우
• 가장 뒤의 노드를 삽입하는 경우

가장 앞의 노드를 삽입하는 경우

head == NULL , 즉 연결리스트가 비어있는경우에는 그날 head = (새 노드의 주소)를 넣어주면 된다.

head != NULL 인 경우에는 앞에 넣으려는 노드에 원래 첫 번째에 있던 노드의 주소를 추가하고 head에 넣으려는 노드를 추가해준다.

 

중간의 노드를 삽입하는 경우

중간에 삽입하기 위해서는 뒤가 될 노드에를 넣을 노드가 가리키도록 바꿔주고 앞이 될 노드에는 넣을 노드의 주소를 연결해주면 된다.

다만 이를 거꾸로 하면 뒤에 올 노드의 주소의 상실이 생기니 조심하자.      

 

가장 뒤의 노드를 삽입하는 경우 

마지막에 추가할 노드에 대한 주소를 원래의 마지막 포인터가 이를 가리키도록 설정해주면 된다. 

 

연결리스트 의 삭제

연결리스트의삭제도 크게 세가지로 나눌 수 있겠다.

• 가장 앞의 노드를 삭제하는 경우
• 중간의 노드를 삭제하는 경우
• 가장 뒤의 노드를 삭제하는 경우

가장 앞의 노드를 삭제하는 경우

head가 삭제하는 노드가 가리키고 있는 주소를 가리키게 하고, 삭제하고자 하는 노드의 주소를 NULL로 바꾼다.

그 후 삭제하고 자 하는 노드를 free시켜주면 된다. 

 

중간의 노드를 삭제하는 경우 && 가장 뒤의 노드를 삭제하는 경우 

1,2,3 순서로 노드가 있고 2를 삭제하고 싶을 때 1의 next에 3의 주소를 저장하고 2의 주소를 NULL로 바꾸면 된다.

그리고 2를 free해준다.

즉 만약 content를 통해 삭제하고자 하는 노드를 탐색할 경우 1노드를 가리키는 포인트, 2노드를 가리키는 포인터, 총 2개의 포인터가 따로 필요하다.