[자료구조] 연결 리스트(Linked List) 개념 이해하기

코딩하는곰곰 2022. 2. 7. 20:00

연결 리스트(Linked List)란?

각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 데이터 구조이다.

여기서 노드(node)란 데이터 연결될 다음 데이터데 대한 주소를 저장하기 위한 <데이터, 주소>의 단위구조를 말한다. 데이터의 값을 저장하는 데이터 필드(Data Field)와 다음 노드의 주소를 저장하는 링크 필드(Link Field)를 가진다.

따라서 순차 자료구조 방식과 다르게 데이터의 물리적 순서와 논리적 순서가 일치할 필요가 없다.

#노드 구조 이미지 추가

선형 리스트와는 달리 노드의 중간지점에서도 자료의 삽입, 삭제 연산이 O(1)의 시간에 가능하다. 중간에 데이터를 삭제해도 노드의 링크 필드가 가지는 주소 값을 바꿔주면 다음 데이터와 연결할 수 있기 때문이다. 따라서 오버헤드도 발생하지 않는다. 순서를 가진 데이터를 보관하나 데이터의 삽입과 삭제가 빈번한 경우 링크드 리스트를 사용하는 것이 좋다.

비연속적이므로 리스트를 분리하기 쉽다. 여기서 비연속적이라는 것은 순서가 없다는 이야기가 아니라 데이터를 연속된 기억공간에 두지 않는다는 뜻이다.

하나의 고정크기 메모리 공간을 사용하는 순차 자료구조와는 다르게 크기 변경이 유연해 효율적인 메모리 사용이 가능하다.

#오버헤드에 대해서 링크 추가

논리적 순서와 물리적 순서가 일치하지 않기 때문에 데이터에 접근하기 위해서는 순서대로 접근해야됨으로 특정 위치의 데이터에 접근하는데에는 O(n)의 시간이 걸린다.

순차 리스트는 데이터가 순차적으로 때문에 다음 데이터의 주소를 가지는 노드를 가질 필요가 없다. 반면에 연결 리스트는 다음 데이터에 접근하기 위한 포인터가 필요하므로 추가 공간이 필요하다.

연결 리스트의 삽입

연결 리스트의 삭제

연결 리스트의 종류

단순 연결 리스트

노드가 하나의 링크 필드를 가지는 연결 리스트. 링크 필드는 다음 노드를 가르킨다. 마지막 노드는 항상 NULL을 가르킨다.

#단일 연결 리스트 이미지

이중 연결 리스트

노드가 두 개의 링크 필드를 가지는 연결 리스트. 두 개의 링크 필드는 앞의 노드와 뒤의 노드를 각각 가르킨다. 첫 노드와

#이중 연결 리스트 이미지

원형 연결 리스트

마지막 노드의 링크 필드가 첫 노드를 가르키는 원형 구조의 연결 리스트. 단순 연결 리스와 비슷하지만 마지막 노드가 첫 노드와 논리적으로 연결되어 있다는 점에서 다르다.

#원형 연결 리스트 이미지

#링크 필드가 다음 노드의 주소값을 가진다 == 노드가 다음 노드와 논리적으로 연결되어 있다?

#링크 필드가 다음 노드를 가르킨다 == 노드가 다음 노드와 논리적으로 연결되어 있다?