[자료구조] 링크드 리스트(Linked List), 연결리스트는 무엇일까??

연결 리스트(링크드 리스트) 개요

추상적 자료형인 리스트를 구현한 자료구조이다. Linked List라는 말 그대로 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 구조이다. 이름에서 말하듯이 데이터를 담고 있는 노드들이 연결되어 있는데, 노드의 포인터가 다음이나 이전의 노드와의 연결을 담당하게 된다.

 

리스트의 각 원소는 메모리 상 연속적인 공간에 할당되지 않을 수 있다. 즉, 첫번째 원소의 주소를 알더라도 그 다음 원소의 주소를 단순히 계산할 수 없다는 의미이다. 리스트의 각 원소는 다음 원소를 가리키는 '포인터(Pointer)'등을 사용하여 각 원소의 순서를 구현한다. 리스트는 포인터로 연결하는 특징을 가지다 보니 배열보다 데이터의 삽입/삭제가 빠른 편이다. 삽입과 삭제는 O(1)의 시간에 가능하다는 장점을 갖는다. 앞, 뒤 원소의 포인터만 바꿔주면 되기 때문이다.

 

하지만, 인덱스를 사용하여 특정 원소에 직접 접근이 불가능하기 때문에 원소를 검색하기 위해서는 첫 번째 원소부터 선형 검색(Linear search) 해야하는 단점이 있다. 그렇기 때문에  O(n)의 시간이 걸리는 단점도 갖고 있다.

 

 

 

 

링크드 리스트의 각 원소는 노드(Node)이다. 각 노드는 데이터와 그 다음 노드를 가리키는 포인터(Pointer)를 가지고 있다. 링크드 리스트의 맨 앞과 맨 끝 노드를 각각 머리(Head), 꼬리(Tail) 노드라고 한다. 각 노드의 앞쪽 노드를 전임 노드(Predecessor Node), 뒤쪽 노드를 후임 노드(Successor Node)라고 한다.

 

연결리스트의 종류로는 단순 연결 리스트, 원형 연결 리스트, 이중 연결 리스트가 존재한다.

 

 

 

 

 

 

 

 

베타존 : 네이버쇼핑 스마트스토어