단순 연결 리스트(Singly Linked List)

연결 리스트란?(What is Linked List?)

---

연결 리스트(Linked list)란 링크로 원소들이 연결된 순차 리스트를 말한다. 연결 리스트는 순차 리스트의 삽입삭제 연산에서의 불리한 점을 보완하기 위해 만들어 졌다. 순차 리스트에서 삽입 연산을 하게 되면 중간에 데이터를 집어넣을 때 삽입될 데이터를 위해 공간을 만들어야 한다. 이때 공간을 만드는 과정에서 삽입되는 데이터 뒤에 데이터들이 자리를 옮기기 위한 연산을 취해야 하는데 이는 리스트가 가지고 있는 데이터가 크면 클수록 많은 시간이 걸린다. 삭제 연산도 삭제후 빈 공간을 채우기 위해 자리를 옮기는 과정이 필요하다. 이러한 문제점들을 해결하는 것이 연결 리스트이다.

 

연결 리스트와 순차 리스트의 차이

 

연결 리스트를 이루는 기본적인 단위는 노드(node)이다. 노드는 데이터 필드(data field)와 링크 필드(link field)로 나누어 진다. 데이터 필드는 말 그대로 데이터를 가지는 공간이다. 데이터는 기본적인 자료형부터 사용자가 정의하는 구조체나 클래스까지 확장될 수 있다. 링크 필드는 다음 노드의 주소를 가리키는 공간이다. 이 링크 필드가 연결 리스트의 핵심이다. 링크는 다음 노드를 가리켜 리스트가 연결될 수 있도록 해준다. 이 링크가 노드를 가르키는 방법에 따라 순차 연결 리스트, 원형 연결 리스트, 이중 연결 리스트로 나눌 수 있다.

 

 

노드의 구조

 

단순 연결 리스트(Singly Linked List)

---

단순 연결 리스트(singly linked list)는 연결 리스트중에서 가장 기본적인 연결 리스트이다. 각 노드들은 이전 노드의 링크 필드를 통해 연결되어지며 리스트의 접근은 가장 처음 노드를 가리키는 포인터를 통해 접근하게 된다. 일반적으로 가장 처음 노드를 가리키는 포인터는 리스트의 이름으로 지정한다. 단순 연결 리스트는 아래 그림과 같이 표현할 수 있다.

 

단순 연결 리스트

 

 

단순 연결 리스트는 다음과 같은 기본적인 연산을 가지고 있다.

1. 리스트 생성
2. 노드 삽입
3. 노드 삭제

리스트 생성

리스트를 사용하기 위해서는 먼저 리스트를 가리키는 포인터를 생성해야한다. 필자가 구현한 리스트를 기준으로 설명하기 때문에 개념은 같으나 구현방식에서 오는 약간의 차이는 있기 때문에 이 부분은 비교해가면서 보길 바란다.

 

 노드는 위와 같이 데이터필드와 링크필드를 가지는 구조체로 정의한다. 리스트 생성함수는 헤드노드를 만든 후 노드를 가리키는 포인터를 리턴한다. 포인터는 리스트를 가리키는 포인터이고 포인터가 가리키는 노드는 헤드노드로 이후 연산의 편의성을 위해 포인터가 바로 데이터를 가지는 노드가 아닌 빈 노드를 가리키게 만든다.

 

헤드 노드를 갖는 리스트 생성

 

노드 삽입

리스트의 첫 번째 자리에 노드 삽입

노드를 삽입하는 함수는 3가지로 나누어 설명하겠다. 먼저 리슽의 가장 앞자리에 노드를 삽입하는 과정이다. 가장 앞자리에 노드를 삽입하는 경우 먼저 새로운 노드의 링크 필드가 헤드노드의 링크필드가 가리키는 곳을 가리키도록 만들어 준다. 그러면 새로운 노드와 헤드노드는 모두 삽입하기 이전 헤드노드의 다음 노드를 가리키게된다. 다음 헤드노드의 링크필드가 새로운 노드를 가리키도록 해준다. 그러면 앞자리에 노드 삽입이 되게 된다.

 

1. 노드 생성

 

2. 새로운 노드와 data1노드 연결

3. 헤드노드와 새로운 노드 연결

 

리스트의 마지막 자리에 노드 삽입

리스트의 마지막 자리에 삽입도 기본적인 작동 방식은 위와 같다. 새로운 노드를 생성한 뒤 새로운 노드의 링크 필드는 NULL이 되게 한다. 마지막 자리에 삽입하는 경우는 다음 노드가 없기 때문에 가리킬 수 없다. 다음 삽입하기 전 마지막 노드의 링크필드가 새로운 노드를 가리키도록 한다. 이때 마지막 노드가 무엇인지 찾은 방법은 구현하는 사람에 따라 다르다. 마지막 노드를 따로 저장할 수도 있고 필자처럼 처음부터 찾는 방법도 있다. 후자의 방법은 리스트의 단점을 최대로 이용하는 방법이다. 그렇기 때문에 전자의 방법으로 구현해보기 바란다.(전자의 방법을 쓴 건 리스트의 검색부분을 활용한 것이다.)

1. 새로운 노드 생성

data2노드와 새로운 노드 연결

리스트의 중간 자리에 노드 삽입

리스트의 중간 자리는 조금 복잡할 수 있으니 집중해서 봐주길 바란다. 리스트의 중간 자리에 삽입하는 방법도 위 2가지 방법과 동일하다. 먼저 새로운 노드를 생성한다. 그리고 내가 삽입하고자 하는 자리의 이전 노드를 가리키는 preNode라는 변수와 삽입하고자하는 위치를 가리키는 ptr 변수를 통해 삽입하고자하는 위치를 찾는다. 다음 새로운 노드의 링크필드가 preNode의 링크필드가 가리키는 노드를 가리키도록 한다. 그 후 preNode가 새로운 노드를 가리키도록 한다.

여기서 ptr 변수의 역할은 삽입하고자하는 자리의 노드를 가리키는 변수이다. ptr변수없이도 구현할 수 있으니 구현해보는 것도 좋은 공부가 될 것이다.(노드 삭제 코드를 재활용하느라 ptr변수가 들어간 것이다.)

1. 새로운 노드 생성

2. 새로운 노드와 data2노드 연결

3. 새로운 노드와 data1노드 연결

노드 삭제

노드 삭제 과정도 삽입 과정과 유사한 형태이다. 단지 연결하는 과정이 연결을 끊는 과정으로 바뀐 것일 뿐이다. 먼저 삭제할 노드를 검색한다. 이때 preNode와 ptr변수를 사용하는데 preNode는 삭제되는 노드의 이전 노드를 가리키고 ptr변수는 삭제할 노드를 가리킨다. 다음 삭제할 노드의 링크필드가 가리키는 노드를 preNode의 링크필드가 가리키도록 한다. 그러면 리스트 상에서는 노드가 사라진다. 하지만 프로그램의 관점에서는 아직 노드가 살아있기 때문에 메모리 공간을 차지하고 있다. 이를 삭제하기 위해서 ptr변수를 이용하여 메모리 해제를 해주는 것이다. 왜 preNode로 해제하고 가리키는 방법은 없는지 궁금할 수 있다. preNode로 먼저 해제를 해버리면 삭제된 노드의 다음 노드를 찾을 수 없다. 그러면 리스트가 끊기게 된다.

 

1. 삭제할 노드 검색

2. preNode와 data2노드 연결

3. ptr이 가리키는 노드 삭제

 

단순 연결 리스트 구현

---

구현은 아래 필자의 깃허브에 있으니 참고하길 바란다. 기본적인 원리만 구현을 했기 때문에 실제 사용에는 무리가 있다.참고만 하길 바란다.

GitHub - LimeTree0/Data-Structure