[C언어]38일차 - 링크드 리스트 (이것이 C언어 자료구조 알고리즘이다.)

[C언어]38일차 - 링크드 리스트 (이것이 C언어 자료구조 알고리즘이다.)

 

 

이 장의 핵심 개념 

 

1.리스트의 개념을 이해한다.

2.리스트와 배열의 차이점을 이해한다.

3.링크드 리스트의 개념과 구현을 이해한다.

4.더블 링크드 리스트의 개념과 구현을 이해한다.

5.환영 링크드 리스트의 개념과 구현을 이해한다.

 

 

1.리스트의 개념

 

리스트에 노드를 추가를 하는 연산

노드 사이에 노드를 삽입하는 연산

노드를 제거하는 연산

특정 위치에 있는 노드를 반환하는 연산

 

 

2.리스트와 배열의 차이점

 

배열은 생성하는 시점에 반드시 배열의 크기를 지정해줘야 하고 생성한 후에는 그 크기를 변경할 수 없다는 단점이 있다. 

 

 이런식으로 선언하면 배열에 담을 개수가 실제로 더 많을 수 있고 적을 수 있다.

 

 

 

이 문제를 해결하기 위해 나온 자료구조가 바로 리스트다.

 

리스트는 스택, 큐, 트리와 같은 자료구조의 중요한 기반이 된다.

 

 

 

3.링크드 리스트의 개념과 구현

 

링크드 리스트는 노드를 연결해서 만든 리스트이다.

아래와 같이 데이터를 보관하는 필드, 다음 노드와 연결 고리 역할을 하는 포인터로 이루어진다.

 

 

 

 

리스트의 주요 연산

 

노드 소멸과 노드 삭제는 완전히 다른 연산이다.

노드 소멸은 노드를 메모리에서 없애는 연산, 노드 삭제는 리스트에서 노드를 제외하는 연산이다.

 

 

 

노드 생성/소멸 연산 (잘못된예)

 

 

1.SLL_CreateNode() 함수가 가장 먼저 지역변수 NewNode를 자동 메모리 (스택)에 생성한다.

2.NewData의 Data , NextNode 필드를 초기화 한다.

3.함수 끝에 NewNode의 주소를 반환한다.

 

하지만 MyNode 포인터는 NewNode가 존재하는 메모리의 조소를 갖고 있는것이 아니다.

 

자동 메모리에 의해 제거된 NewNode가 존재했던 메모리의 주소를 담고 있다.

 

그래서 자유 저장소 힙 메모리를 사용하는 방법을 알아 봐야한다.

 

반환형이 void*임

어떤 형식의 데이터든 담을 수 있음.

 

이런식으로 malloc을 사용해서 자유 메모리 힙공간에 객체를 만들어준다.

 

그리고 아래 처럼 free 함수로 메모리를 제거해준다.

 

노드 추가 연산

 

SLL_CreateNode() 함수를 이용하여 자유 저장소에 노드를 생성한 다음, 새로 생성한 노드의 주소를 테일의 NextNode 포인터에 저장하면 된다.

 

호출

 

 

 

 

노드 탐색 연산

 

배열에서서는 어떤 위치에 있는 요소를 취하고 싶을때 해당 요소의 첨자를 입력하면 바로 해당 요소에 접근할 수 있다.

이에 반해 링크드 리스트는 헤드 부터 시작해서 다음 노드에 대한 포인터를 징검다리 삼아 차근차근 노드의 개수 만큼 거쳐야 원하는 요소에 접근 할 수 있다.

 

 

 

노드 삭제 연산

 

노드 삭제 연산은 링크드 리스트 내 임의의 노드를 제거하는 연산이다.

 

삭제하고자 하는 노드를 찾은 후 해당 노드의 다음 노드를 이전 노드의 NextNode 포인터에 연결하면 그 노드를 삭제할 수 있다.

 

 

 

 

 

노드삽입 연산

 

 

 

노드 개수 세기 연산

 

링크드 리스트의 장단점 : 노드의 추가, 삽입, 삭제 연산은 빠르지만 특정 위치에 있는 노드에 접근하는 연산은 느리다.

 

따라서 링크드 리스트는 레코드의 추가, 삽입, 삭제가 잦지만 조회는 드문 곳에서 사용하기 적합하다.