Linked List

linked list: 데이터 요소의 선형 집합으로, 데이터의 순서가 메모리에 물리적인 순서대로 저장되지 않는다.

동적으로 새로운 노드를 삽입하거나 삭제하기가 간편하며, 연결 구조를 통해 물리 메모리를 연속적으로 사용하지 않아도 되기 때문에 관리가 쉽다. 또한 데이터를 구조체로 묶어서 포인터로(Java의 경우에는 포인터가 없기 때문에 레퍼런스로 구현한다.) 연결한다는 개념 또한 다양한 방법으로 활용할 수 있다.

linked list는 array와는 달리 특정 인덱스에 접근할 때 전체를 순서대로 읽어야 하기 때문에 조회에 있어서 O(n)의 시간복잡도가 발생한다. 하지만 첫번째 아이템을 추가 삭제 추출하는 작업은 O(1)의 시간복잡도를 나타낸다.

Linked List의 종류의 예

Singly Linked List

가장 단순한 형태의 Linked List. queue를 구현할때 사용된다.

Doubly Linked List

다음 노드 뿐만 아니라 이전 노드의 참조도 같이 포함하는 이중 연결 리스트. 단순 연결리스트의 경우 삭제 작업이 O(n)의 시간이 걸리지만, 이중 연결 리스트는 O(1)시간으로 처리할 수 있다.

단, 삽입 정렬에 있어서 작업량이 증가하는 단점이 있다.

Circular Linked List

단순 연결 리스트처럼 마지막 원소가 Null을 가르키는 게 아닌 첫번째 원소를 가르킨다.