--------------------------------------------
--------------------------------------------
연결리스트는
배열의 한계를 극복해줍니다.
배열은 길이가 한정되어있지만
연결리스트는
동적할당을 이용하여 계속적으로 요소를 추가하기 때문에
길이의 제한이 없습니다.
--------------------------------------------
--------------------------------------------
우선 연결리스트를 만들기 위해
이런 구조체가 필요 합니다.
구조체의 요소는
데이터가 들어갈 정수 변수와
다음 구조체 요소의 주소를 가지는 구조체 포인터 입니다.
--------------------------------------------
이 구조체 포인터에
다음 노드의 주소가 담깁니다.
--------------------------------------------
연결리스트의 사용법은 동적할당으로
노드를 생성하여
연결하는 방식입니다.
--------------------------------------------
이렇게 첫번째 노드를 만들고
--------------------------------------------
추가하는 방향은 설정하기 나름이고
여기선 오른쪽 방향으로 추가되도록 해주었습니다.
--------------------------------------------
계속 이런식으로 오른쪽에 추가해서 이어줍니다.
그러므로 연결리스트는 배열과 달리 길이의 제한이 없습니다.
원하는 개수만큼 계속 추가할수 있기 때문입니다.
다만 메모리 제한은 있습니다.
--------------------------------------------
--------------------------------------------
이런식으로
동적할당을 이용해서 노드를 생성하고 주소를 반환하여
기본적인 노드 구조를 만들어 주고
데이터를 넣습니다.
--------------------------------------------
그 다음
노드 N1의 구조체 포인터 LINK에
다음 노드의 주소값인 N2값을 넣고
노드 N2의 구조체 포인터 LINK에
다음 노드의 주소값인 N3값을 넣고
노드 N3의 구조체 포인터 LINK에
NULL값을 넣어서
끝맺음을 해줍니다.
--------------------------------------------
많은 일반적인 책에선 생략된 형태가 많이 나오기 때문에.
제대로된 이해를 위해서
좀 더 정확한 형태를 그려보겠습니다.
--------------------------------------------
밑줄친 이 부분은
동적할당으로 힙 영역에 노드를 생성해서
주소를 노드 포인터에 반환한 것이므로
노드 포인터가 동적할당된 메모리 영역을 가리키는 모양이 됩니다.
--------------------------------------------
즉 이런식으로
노드 포인터 N1이 힙영역 메모리를 가리키는 모양이 됩니다.
--------------------------------------------
--------------------------------------------
이런식으로
동적할당으로 노드를 생성한다음
데이터를 넣어줍니다.
--------------------------------------------
이것을 그림으로 나타내면
이렇게 그릴수 있습니다.
--------------------------------------------
다음으로
노드끼리 연결해줍니다.
자세하게 살펴보면
--------------------------------------------
N1의 링크에는 다음 노드의 주소인
N2값이 들어갑니다.
N2에는 동적할당한 노드의 주소가 들어있습니다.
이렇게 하면 노드 N1과 노드 N2가 연결됩니다.
노드 N1의 링크가 노드 N2를 가리키게 됩니다.
--------------------------------------------
이런식으로
노드 N1과 노드 N2가 연결됩니다.
--------------------------------------------
N2의 링크에는 다음 노드의 주소인
N3값이 들어갑니다.
N3에는 동적할당한 노드의 주소가 들어있습니다.
이렇게 하면 노드 N2와 노드 N3가 연결됩니다.
노드 N2의 링크가 노드 N3를 가리키게 됩니다.
--------------------------------------------
그림을 그리면 이런식으로 표현할 수 있습니다.
--------------------------------------------
마지막으로 N3의 링크에 널 포인터를 넣어주고 마무리를 합니다.
일반적으로 노드의 끝에는 널포인터를 넣어서 마무리를 하게 됩니다.
일종의 마감처리라고 할 수 있습니다.
--------------------------------------------
그러면 비로소 이렇게 마무리가 되고
모든 노드들이 안정적으로 연결 되었습니다.
이 노드 구조체를 이용한 연결리스트 구조는
동적할당을 이용한 자료구조 구현의 기본재료가 됩니다.
그러니 정확하게 그림으로 이해하고 많이 활용하면 되겠습니다.
--------------------------------------------
'자료구조' 카테고리의 다른 글
| [자료구조] 8장. 연결 리스트 스택 (지역변수) (Stack Linked List) (0) | 2020.04.10 |
|---|---|
| [자료구조] 7장. 연결 리스트 스택 (전역변수) (Stack Linked List) (0) | 2020.04.10 |
| [자료구조] 5장. 원형 큐(Queue) 구현 (배열) (0) | 2020.04.09 |
| [자료구조] 4장. 선형 큐(Queue) 구현 (배열) (0) | 2020.04.09 |
| [자료구조] 3장. 큐(Queue) 설명 (0) | 2020.04.09 |
