연결리스트는 뭐야?

연결 리스트는 구조를 봐도 알 수 있듯이 연결되어 있는 리스트이다. 연결 리스트는 배열과 거의 같은 기능을 한다. 2가지 자료 구조에 대해서 장단점을 연결 리스트를 중점으로 알아보겠다.

 

연결 리스트의 장점

• 연결 리스트 중간에 값을 삽입하는 것이 편한다.
• 데이터를 저장할 때마다 동적으로 공간을 만들어서 쉽게 추가할 수 있다.

연결 리스트의 단점

• 데이터와 함께 포인터를 저장해야 하므로 메모리를 많이 차지한다.
• 배열에 비해 상대적으로 구현이 어렵다.
• i번째 데이터에 대해서 순차적으로 탐색을 해야 한다.

장점과 단점을 잘 비교하여 필요한 자료 구조를 잘 선정하면 될 것 같다. 다음은 연결 리스트의 구조체이다.

typedef int element;
typedef struct {
    element data;
    struct ListNode *next;
} ListNode;

data는 해당 노드의 값을 저장하는 부분이고, next는 다음 노드를 가리키는 포인터이다. 연결 리스트에서는 삭제와 생성 부분이 주요하게 다뤄진다. 따라서 비교적 쉬운 마지막 노드 삭제, 생성부터 중간 노드 삭제 생성까지 시각화 자료를 통해 알아보겠다.

 

다음은 마지막 노드에 연결 리스트의 노드를 생성하는 것을 시각화한 자료이다. 검은색 부분은 수정이 없는 부분이고, 빨간색 부분은 수정이 발생한 부분이다.

마지막 노드에 생성

마지막 노드에 노드를 생성하는 것은 head를 따라 마지막 노드까지 간 후에 새로운 노드 2를 생성한 후에 1의 다음 노드로 지정해주면 된다.

 

다음은 중간 노드에 새로운 노드를 생성하는 것을 시각화한 자료이다.

중간 노드에 생성

마찬가지로 노드 3을 생성한 후에 노드 2와 새로 생성된 노드 3의 다음 노드를 지정해주는 과정이 필요하게 된다. 다음 노드를 지정하는 과정은 다음의 순서를 따른다.

1. 새로 생성된 노드 3이 노드 2의 다음 노드를 가리키게 한다.
2. 노드 2의 다음 노드를 새로 생성된 노드 3으로 설정한다.

위의 순서를 지키지 않고 2번을 먼저 실행하게 되면 노드 2의 다음 노드에 대한 포인터를 잃어버리게 되어 새로 생성된 노드 3의 포인터가 가리킬 곳을 찾지 못하게 되게 된다. 따라서 포인터를 가리키는 순서를 잘 지켜야 한다.

 

다음은 마지막 노드 삭제에 대해 알아보겠다.

마지막 노드 삭제

마지막 노드 삭제는 노드 2의 값을 포인터에 저장해두었다가 노드 1의 포인터를 NULL로 변경한 후에 노드 2가 차지하고 있는 메모리를 해제해주면 된다.

 

다음은 중간 노드 삭제에 대해 알아보겠다.

중간 노드 삭제

앞서 3가지 방법 중에 가장 복잡한 구조를 띄고 있다. 중간에 있는 노드를 삭제하기 위해서는 총 4가지 순서를 따르게 된다. 순서는 다음과 같다.

1. 노드 3의 포인터를 삭제될 노드 6의 포인터로 변경한다.
2. 삭제될 노드 6의 포인터를 NULL로 변경한다.
3. 삭제될 노드 6의 메모리 공간을 해제한다.

이렇게 단순 연결 리스트의 구조체와 생성과 삭제에 대해 알아보았다. 위와 같은 연결 리스트 구조를 제외하고 원형 연결 리스트와 이중 연결 리스트와 같은 구조 또한 존재하니 부족한 부분은 찾아서 공부해보는 것을 추천한다.