[자료구조] Linked list의 구조

 

---

Linked list를 이해하기 위한 사전지식을 간단히 정리해보자.

 

Storage (hdd, ssd, 플로피디스크) - 데이터를 이곳에 저장하게 된다.

ㅇ 특징: 가격이 저렴하다. 용량이 크고, 전원이 꺼져도 데이터 저장되어 있다.

 

Memory

ㅇ비싸고, 용량이 스토리지보다 작고, 끄면 데이터가 휘발된다.

ㅇ스토리지보다 훨씬더 빠르게 데이터를 저장하고 가져온다.

 

Cpu 생각하고 계산하고 연산하는 것..

ㅇ처리속도가 가장 빠르다. -> 상대적으로 스토리지가 너무 느리다. 그래서 스토리지에 있는 데이터를 메모리로 넘긴 후, 그 메모리에 있는 데이터를 CPU가 처리하는 방법으로 동작한다

 

 

그래서 데이터 스트럭쳐의 관심 대상은 메모리다!

메모리를 효율적으로 사용하는 것이 자료구조에 가장 중요하고, 공부하는 이유이다. 

 

메모리에는 주소가 있고, 주소가 가르키는 각각의 위치에 데이터가 저장되어 있다.

각각의 주소에 접근할 때 걸리는 시간이 동일하다는 특성을 가지고 있다.

이것이 바로>>Random Access Memory --> RAM 저장장치!

주소를 알고있다면 굉장히 빠르게 데이터를 가져올 수 있다는 것이 RAM의 특징이다.

이런 특징을 잘 활용해야 우리가 만든 애플리케이션이 빠르다.

 

아래 그림은 메모리상에서 봤을때 모습을 건물에 비유한 그림이다.

ArrayList 엘리먼트들이 메모리상에 실제로 연속적으로 붙어있다.

LinkedList 엘리먼트들은 흩어져서 메모리에 저장되지만, 실제로는 연결이 되어있다.

 

연결되어 있다는 특성을 가진다! 그래서 사실 엘리먼트라는 용어대신에

node나 vertex라는 말을 더 즐겨 사용한다.

마디, 교점, 정점, 꼭짓점... 하나같이 연결이라는 것과 연관되어있다. 

 

---

//링크드리스트의 이해

하나의 노드 안에는 두개의 필드(변수)가 있다.

1. 저장되는 실제 값 (Data field)

2. '노드 다음 노드가 무엇인가?'를 알기 위해서

링크필드라는 변수에 다음 노드가 무엇인가가 저장이 됨 (Link field)

++첫번째 노드가 무엇인가를 우리가 알 수 있어야 한다. 

그래야 링크필드를 통해 다음 노드로 가고.. 또 다음 노드로 가고 하니까..

>> 바로 이 정보를 헤드필드에 넣는다!

첫번째 노드가 무엇인가에 대한 데이터를 가지고 있는 것이 헤드다.

 

 

 

---

다음 시간에는

Linked list에 데이터를 추가하고 삭제하고 조회하는 것들이 어떻게 동작하는지

visualgo.net을 이용해서 살펴보겠다.

 

 

참고강의 https://programmers.co.kr/learn/courses/17/lessons/805