저별이의 초보 코딩

알고리즘 중에 접할 수 있는 개념 중 연결리스트가 있다.

연결리스트라는 말이 낯설 수도 있고 해봤을 수도 있다.

구조체와 포인터라는 이름으로 배우기도 했는데 연결리스트라는 개념을 확실히 알아보고자 한다.

먼저 연결리스트는 데이터가 담긴 노드(메모리 공간)를 일렬로 해놓은 것을 의미한다.

그리고 이 노드들은 포인터를 통해 연결되어 있다.

그래서 리스트의 중간지점에 노드를 손쉽게 추가하거나 삭제가 가능하다.

이 특징 때문에 크기가 고정되어있지 않으며 확장, 축소를 위해 메모리 할당을 통해 진행한다.

하지만 기존 배열과 달리 특정 노드를 찾기 위해 모두 검색해야 한다.

그렇기 때문에 만약에 끝에 있는 노드를 찾고 싶다면 처음부터 끝까지 검색해야 할 것이다.

앞에서 언급했듯이 크기가 고정되어 있지 않기 때문에 노드에 메모리를 할당해주어야 한다.

next 멤버에 다음 노드의 메모리 주소를 저장하고 data 멤버에는 데이터가 저장된다.

만약 마지막 노드라면 next는 아무것도 가르키지 않으므로 NULL을 저장해주어야 한다.

메모리 할당 방식은 'struct 구조체 이름 *할당할 이름=malloc(sizeof(struct 구조체이름));' 이다.

그리고 next나 데이터에 저장할 내용은 '할당할 이름->next or data=담을 정보'를 이용해 담을 수 있다.

그러면 이제 대략적인 연결리스트 개념을 알아봤으니 노드의 추가, 삭제 방식을 알아보고자 한다.

앞에서 언급한 것도 있지만 그래도 노드 추가에 대해서 한번 더 알아보자

일단은 새로운 노드를 생성해주는 것은 앞에처럼 할당해주는 방식을 사용한다. 

크기는 물론 구조체 크기 만큼 할당해주어야 한다.

그리고 새로운 노드의 next에는 기존에 그 곳을 가르키는 앞의 next가 가르키도록 해주어야 하고

새로운 노드의 data에는 data를 담아야 할 것이다.

그러면 기존 앞에 있던 노드의 next는 새로운 노드를 가르켜야 한다.

이렇게 해주면 새로운 노드를 추가할 수 있다.

이제 노드를 삭제하는 방식을 알아보자

삭제하고자 하는 노드는 기존 target에서 next로 가르키고 있던 데이터이다.

그리고 target의 next는 삭제하고자 하는 노드의 next를 가르키도록 해야 사이에 있는 삭제하고자 하는 노드가 빌 수 있다.

그리고 최종적으로 free를 통해 메모리 할당을 해제해주면 된다.

이 과정을 통해 연결리스트를 구현할 수 있다.