[자료구조 /알고리즘] Linked List란?

Linked List는 컴퓨터에 자료를 저장하는 구조의 종류중 하나이다.

 

생긴모양은 배열과 비슷하게 생겼다.

배열과의 가장큰 차이는 배열은 미리 공간을 정해야한다.

무슨 뜻인가 하면, 내가 어떤 크기의 데이터를 저장할지 미리 선언을 해줘야한다.

 

하지만 Linked List(연결 리스트)의 경우에는 그럴 필요가 없다.

위의 그림을 보면 15|3600 을  풀어보면 해당 노드는 15라는 숫자를 가지고있고, 그다음 숫자는 3600번지에 담겨있다.

라는 의미가 된다.

3600번지를 가보면 3|4000 이 담겨있는데, 3이라는 숫자를 가지고있고, 다음 숫자는 4000번지에 담겨있다는 뜻이다.

 

이처럼 중간에 삽입, 삭제를 할수있다는 장점이있다.

단점으로는 삽입,삭제시 다음 노드와 이전 노드의 주소를 담아줘야한다.

 

15|3600과 3|4000 사이에 7이라는 숫자를 담고싶으면 7|? 여기에 15가 가지고있는 3600을 알려줘야하고,

15|? 에는 3600이라는 숫자 대신 7을 가르키는 주소를 알려줘야한다.

 

반대로 삭제시에도 비슷한 과정을 거쳐야한다. 

 

다음주소와, 자신의 주소를 할당하지 못하면 리스트가 끊겨버린다.

 

 

※프로그래밍에서는 c나 c++에서는 삭제한 노드를 메모리에서 해제해줘야하고, java는 가비지컬렉터가 있기 때문에 사용하지 않는 메모리는 자동 해제한다.

 

 

즉, Linked List는 사용하는데 불편함은 있지만, 크기가 가변적이기 때문에 배열보다 좋고, 반대로 배열은 고정크기지만 번거로움이 적다.(물론 배열도 고정크기 이외의 단점이 존재한다.)

 

 

 

반응형