c언어 연결 리스트에 대하여 알아보기

c언어 연결 리스트에 대하여 알아보기

네 안녕하세요, 이번 포스팅에서는 연결 리스트에 대하여 알아보도록 하겠습니다.

연결 리스트 역시 c언어 프로그래밍을 할 때 빼놓을 수 없는 요소입니다.

그만큼 중요한 역할을 하기 때문에 잘 알아두셔야 나중에 잘 쓸 수가 있습니다.

그럼 지금부터 시작하도록 하겠습니다.

 

1. 연결 리스트란?

우리는 지금까지 대량의 데이터를 저장하는 데에는 주로 배열을 이용했었습니다.

그렇지만 배열은 구현이 간단하다는 장점이 있지만,

단점으로는 데이터를 받을 수 있는 크기가 고정이 된다는 것입니다.

그래서 추가적인 데이터를 넣고 싶은데 공간이 없다면 문제가 발생합니다.

물론 더 큰 배열을 만들어서 배열 속에 있는 데이터들을 전부 복사하여 옮기는 것도 방법이지만,

이 방법은 cpu를 혹사시킬 수 있기 때문에 결코 효율적인 방법은 아닙니다.

데이터를 계속 뒤로 밀어내고, 여기저기 이동을 시켜야 하기 때문에 결코 간단한 일은 아니기 때문입니다.

그래서 이러한 단점을 보완하기 위에서 쓰는 것이 연결 리스트(linked list)이고,

이 연결 리스트 자료 구조에서는 각각의 원소가 포인터를 사용하여 다음 원소의 위치를 가리키게 됩니다.

그래서 다음 자료가 있는 위치까지 줄로 연결되어 있는 것과 같은 구조로 되어있습니다.

또한 그러한 줄을 포인터가 담당하게 되는 것이지요.

그래서 이럴 경우에 데이터의 삽입 및 수정, 그리고 삭제가 편해집니다.

데이터를 추가할 때는 포인터만 추가해주면 되고,

데이터를 삭제할 때는 포인터를 지워서 연결을 끊어버리면 되기 때문입니다.

 

2. 연결 리스트의 구조

연결 리스트의 단위는 노드(Node)인데,

이 노드들의 집합이 바로 연결 리스트 입니다.

그리고 이 노드들은 데이터 필드와 링크 필드로 되어있습니다.

반응형

 

2 - 1. 데이터 필드

데이터 필드는 우리가 저장하고자 하는 데이터가 들어갑니다.

데이터에는 여러 가지 자료형들이 들어갈 수 있습니다.

 

2 - 2. 링크 필드

링크 필드는 다른 노드를 가리키는 포인터가 저장이 됩니다.

이 링크 필드가 바로 연결 고리의 역할을 하게 됩니다.

이 연결 리스트에서는 각 노드의 첫 노드를 알아야 전체 노드에 접근이 가능한데,

이러한 제일 첫 노드를 가리키는 변수를 '헤드 포인터(Head Pointer)'라고 합니다.

그래서 연결 리스트의 이름은 헤드 포인터와 동일합니다.

또한 여기서도 연결 리스트의 끝은 NULL이 차지를 하여 데이터가 끝이 났다는 것을 표시합니다.

 

3. 연결 리스트의 단점

하지만 이렇게 편리한 만큼 단점도 존재합니다.

일단 한 노드에 필드가 두 개이기 때문에 링크 필드를 위한 공간이 추가적으로 필요하고,

배열에 비해 더 복잡한 구조를 가지고 있어서 프로그래밍을 할 때 많은 에러들과 마주할 가능성이 높아집니다.

 

여기까지 연결 리스트에 대하여 알아보았습니다.

다음 포스팅에서는 연결 리스트를 생성하는 방법에 대하여 알아보도록 하겠습니다.

긴 글 읽어주신 독자분들께 진심으로 감사드립니다~