[04-1] 연결 리스트란?

Linked List(연결 리스트)는 Node(노드)로 구성되어 있다.

이 Node를 어떻게 구성하냐에 따라 Tree가 될 수도, Graph가 될 수도 있다.

 

Array 리스트는 파이썬에 리스트로 구현되어 있기 때문에 따로 구현을 하지 않았지만, Linked list의 경우 직접 구현하는 것이 매우 중요하다!

 

Linked List?

Node 구조가 연결된 형식으로 저장된 구조로, 데이터값과 Next node의 주소값을 저장한다.

 

Linked list

Linked List의 구조는 다음과 같다. 어디서 많이 본 것 같은데..

이것을 보니까 블록체인의 구조가 떠올랐다. 블록체인은 이전 해시값을 갖고 있는 차이가 있지만, 어쨌든 연결되어 있지 않은가? 그래서 Node라고 하는것인가 싶기도

 

그렇다면 리스트랑 차이는 무엇일까?

리스트는 메모리에 연속적으로 저장되어 있다. 즉 물리적으로 연결되어 있는 것이다.

하지만! 연결 리스트는?

물리적인 연결이 아니라 논리적인 연결이다. 사진으로 봐보자.

물리적 비연속, 논리적 연속

 

연결 리스트는 논리적으로 연속성을 갖고 있어서, address 정보를 가지고 있어야 한다.

그래서 메모리 사용이 자유로울 수 밖에 없다. 굳이 크게 자리를 잡지 않아도 되니까~ 조금 더 최적화되서 사용할 수 있다는 것이다.

 

Linked List를 만들기 위한 조건

1. Node를 구성해야한다.

2. Node는 연결되어야 하며, Linked List의 필수 조건인 head가 필요하다.

3. head는 첫번째 노드를 가르켜야 한다

 

종합해보면 다음과 같다.

 

헤드를 통해서 첫번째 노드를 찾을 수 있고, 그렇게 된다면? 2번째 노드는, 마지막 노드는 시간은 걸려도 찾아갈 수 있다.

그래서 head를 가르키는게 매우 중요하다.

 

내식으로 정리해보면

일반 배열처럼 딱 붙어서 위치하는건 아니지만 서로 연결되어 있는 것.

즉 출석번호로 줄세워 놓지 않아도, 우리반에서 내 뒤에 애만 기억하고 있으면 된다는 것이다. 그리고 맨 앞에 애가 우리반대표인거고.. 그러면 밖 어디서라도 맨 앞에애만 찾으면 너 다음을 데리고와~ 그다음을 데리고와~ 이렇게 해서 어떤 100번째, 1,000번쨰 리스트여도 결국 찾을 수 있다는 것이다.

다만 다른점은? 기존의 리스트는 딱 붙어 있으니까 random access를 통해서 100, 1,000번을 아주 쉽게 찍었다.

하지만 연결 리스트는 1번 다음 2번, 2번다음 3번, 3번 다음 4번 ... 이렇게 찾아야하니까 아주 복잡하겠구만!

 

Linked List 총정리

 

장점

1. 메모리 활용이 자유롭다.

2. 리스트에 국한되지 않은 활용이 가능하다.

 

단점

1. Address 값을 가져야하니까 용량이 커진다!

2. 구현하는 코드가 복잡해진다.

3. 리스트가 길어질수록 시간이 오래걸린다.

 

총평

복잡해지고 용량이 커지지만, 그만한 가치가 있는 자유로운 녀석