파이썬 자료구조 linked list (개발남노씨 코테 인강 필기)

linked list는 Node라는 구조체가 연결되는 형식으로 데이터를 저장하는 자료구조이다. 

Node는 데이터 값과 next node의 주소값을 저장한다. 

 

linked list는 메모리 상에서는 비연속적 저장되어있지만 

각각의 node가 next node의 메모리 주소값을 가리킴으로써 

논리적은 연속성을 갖게 된다. 

 

 

 

Array list는 연속성 유지하려면 순차적으로 저장해야하지만

linked list는 자유롭다. 

주소값을 함께 저장하기 때문에! 근데 그만큼 데이터당 차지하는 메모리가 더 커지게 된다. 

 

linked list 구현시 

1. head값을 가져야함!!

 

2. head가 linked list의 첫번째 노드값을 가리켜야한다!

이렇게 되면 어느 인덱스에 있는 데이터에도 접근할 수 있다.

 

3. 마지막 노드는 다음 메모리주소가 0(none)이어야한다.

 

 

 

 

linked list의 가장 간단한 연산자 append()

get() 특정 index에 저장되어있는 값을 가져오는 연산자.

 

실제 구현시 

양방향으로 왔다갔다하는 양방향 doubled linked list도 있음