Algorithm Make a linked list

알고리듬 Make a linked list를 알아보겠습니다.

​
링크드 리스트는 일반 배열과 달리 주소가 분산되어서 저장됩니다. 일반 배열은 같은 저장 공간 안에 옹기종기 모여있습니다. 그래서 검색과 메모리 측면에서는 좋지만, 삽입, 삭제가 어렵습니다.
링크드 리스트는 다음 주소를 가지고 있기 때문에, 중간에 삽입, 삭제가 자유롭습니다. 저장된 다음 배열의 주솟값만 변경시키면 되기 때문입니다.
​
0, 1, 2, 3으로 구성된 링크드 리스트가 있다고 칩시다. 아래의 그림과 같습니다.
HEAD는 처음을 가리킵니다.

오늘은 삽입, 삭제 이러한 부분을 다루는 것이 아니라 그냥 기초적인 동작 구조를 구현할 겁니다.

사실 파이썬의 list 자체가 링크드 리스트라서 구현할 필요는 없지만, 개념은 알아두면 좋으니까요.

​

​

먼저 노드를 만듭니다.

여기에는 값과 다음 노드가 저장됩니다.

링크드 리스트를 만듭니다. 여기에는 헤더와 나머지 노드들을 저장합니다.

14 번째 줄에서 처음 입력되는 값이면 head와 rest에 모두 처음 노드를 넣습니다.

두 번째부터는 18 번째 줄에서 처음 node의 next에 두 번째 노드가 들어가고 그다음 rest를 두 번째 노드로 만듭니다.

세 번째에는 두 번째 노드의 next에 세 번째가 들어가고, rest가 세 번째 노드로 됩니다. 이런 식으로 계속 추가해 줍니다.

출력해 봅시다.

끝.

카테고리: Algorithm