[Data Structure] Linked List

링크드 리스트, 연결형 리스트라고 부르는 자료구조이다. 사실 자료구조라고 하기엔 애매한 감이 있지만 배열과 더불어 후에 서술할 다른 자료구조들의 바탕이 되는 자료구조이기 때문에 개념을 집고 넘어가야 할 필요성이 있다.

 

구조

 

링크드 리스트의 구조

 

데이터와 주소를 담는 공간으로 이뤄진 노드들의 연결이다. 

 

주소는 자신의 뒤에 오는 노드의 주소를 담고 있고 때문에 노드를 하나 하나 거쳐서 순차적으로 접근하는 구조를 가지고 있다.

 

배열은 시작 주소로부터 일정한 크기의 데이터 나열로 된 구조이지만 연결형 리스트는 메모리 주소가 이어진 구조가 아니라 메모리 내에 여러 곳에 분산적으로 퍼져 있는 구조이다.

 

자신의 뒤로만 접근이 가능하면 싱글, 앞뒤로 접근이 가능하면 더블 링크드 리스트라고 한다.

 

링크드 리스트의 가장 앞 부분을 헤드/머리 노드라고 하고 가장 끝 부분을 테일/꼬리 노드라고 한다.

 

특정 노드로의 임의 접근은 불가능하며 오로지 헤드나 테일 노드에서 시작하여 접근이 가능하다.

 

 

장점

 

노드의 추가/삭제, 삽입이 빠르다.

 

링크드 리스트는 주소로 연결된 비선형적 구조이기 때문에 배열처럼 중간에 데이터가 추가되고 삭제가 된다 하더라도 구조 자체에 큰 변화가 생기지 않는다. 단순히 삽입 혹은 삭제되는 위치에 있는 노드의 앞뒤 노드의 주소만 바꿔주면 되기 때문에 데이터의 추가/삭제, 삽입이 빠르다.

 

 

노드의 추가

 

단점

 

특정 노드 탐색에 오랜 시간을 소모한다.

 

앞서 말한 대로 링크드 리스트는 주소를 타고 넘어가는 구조이기 때문에 특정 노드의 임의 접근이 불가능하다. 만약 자신이 특정 노드를 찾고 싶다면 검색 함수를 통해 노드의 시작, 혹은 끝 부분에서 순차적으로 접근을 하여 확인해야 한다.

 

 

환형 링크드 리스트

 

자신의 앞뒤로 접근이 가능한 것이 더블 링크드 리스트라고 했는데, 이 경우 헤드 노드는 자신의 앞이 없고, 테일 노드는 자신의 뒤 노드가 없다. 만약 헤드와 테일 노드가 서로 연결이 되어 있다고 하면 이는 환형 링크드 리스트이다.

 

환형 링크드 리스트