연결리스트(Linked list) 개념 정리

어떤 댓글에서 이런 문구를 봤습니다.

'자료구조와 알고리즘 공부를 하지 않는 것은 운동선수가 오래달리기를 싫어하는 것과 같다' 라고..

평소에도 필요성을 느끼고 있었던터라 뼈맞은 느낌이였어요.

한때 알고리즘을 공부했었지만 자료구조와 알고리즘 패턴에 대해 개념을 정확히 짚고 넘어가지 않았더니,

이 지식이 마치 공중에 흩날리는 꽃가루처럼 제 머릿속에 사라져버리더라구요 하하..

그래서 첫번째 순서로 오늘은 Linked List에 대해 공부해본 내용을 정리해보았습니다 !!

 

Linked List란 무엇일까 ?

컴퓨터에 정보를 저장하는 자료구조 중의 하나.

- 일렬로 연결된 데이터를 저장할 때 사용.

- 다음 데이터의 주소를 갖고 있는 구조.

 

선형 리스트(Linear List): 배열을 기반으로 구현된 리스트(배열 리스트)

연결 리스트(Linked List): 노드의 연결로 구현된 리스트

출처: https://boycoding.tistory.com/33

 

어디에 사용할까 ?

길이가 정해지지 않은 배열을 조작해야 할 때 사용하면 좋다.

JS에서는 포인터개념이 없고, 배열의 크기가 유동적으로 변하는 것이 가능하기 때문에 중요성이 모호해 보인다. 하지만 Go와 같은 포인터개념이 뚜렷한 언어에서는 이것에 대한 필요성과 역할이 확실히 와닿는다고 한다.

 

 

동작원리 ?

배열은 방 크기가 정해져 있어 추가로 값을 입력하고 싶을 때 늘릴 수가 없다.

 

 

이 때,

1. 새로운 노드가 이전번호를 갖고,

2. 이전 노드에게 다음 노드는 새로운 노드라는 것을 지정해준다.

 

 

반대로 노드를 빼고 싶을 땐,

이전노드에게 다음노드가 몇번인지 새롭게 지정해주면 끝.