[DS] 링크드리스트

노드

데이터를 저장하는 최소 단위

배열에서 노드는 각각의 변수 1개(1칸)을 뜻한다.

 

 

 

링크드리스트

링크드리스트란 한 노드가 노드를 가르키고 있는 자료구조

여러개의 노드로 이루어져 있다.

 

링크드리스트 한 노드가 노드를 가르키는데

그 한개를 노드라고한다.

구조체 (클래스) 포인터를 이용해서 구현한다.

 

 

배열 vs 링크드리스트

배열의 단점

10칸 짜리 배열을 만들었는데 ex) int arr[10];

내가 데이터를 12칸 쓰고싶으면 쉽지가 않다.

12칸짜리 배열을 만들어서 복사해주면되긴하는데

연산이 너무 많아지기에 비효율적이다.

링크드리스트는 실행도중에 추가적으로 데이터를 추가해줘도

큰 부담이 없다.

노드만 생성해주고 주소만 연결해주면 되니까

중간에 데이터를 삽입하건 삭제하여도 큰 부담이 없다.

링크드리스트를 써야 할떄는 실행도중에 데이터가 자주 삽입되거나 삭제될떄

사용하면 좋다.

 

 

연습문제1

동굴 탐험하기

new / malloc을 이용해서 위와같은 노드를 구성해

while문을 이용해서 처음부터 끝까지 출력하라.

 

 

풀이과정

 

출력