Linked List Data Structure

 

 

 

 

 

Linked List

 

1. 데이터 물리적 배치에 따라 순서가 지정되지 않는 선형 연결 구조

 

 

 

 

 

 

 

 

어떤 게 포함되어있나?

 

 

노드가 포함되어있으며(보편적으로 node, element라 표현)

노드에는 현재 데이터와 다음 데이터의 pointer(위치정보)를 포함

 

 

 

 

 

 

 

 

 

특징

 

 

 

 

1️⃣

동적인 자료구조, 데이터를 메모리에 동적으로 할당 가능 애플리케이션에서

사용할 요소의 수를 가늠할수 없을 때 유용

https://www.geeksforgeeks.org/what-is-dynamic-memory-allocation/

 

 

2️⃣

스택과 큐같은 추가적인 자료구조 구현에 좋습니다.

 

 

3️⃣

매우 큰수의 연산 시 하나의 노드가 하나의 숫자를 담당하여

연산을 수행 할 수 있습니다.

 

how?     

https://www.geeksforgeeks.org/add-two-numbers-represented-by-linked-lists/

 

 

 

 

4️⃣

삭제, 삽입시 시간복잡도 O(1)을 가진다. 해당 작업(삭제, 삽입) 수행 시

이전 노드와 다음 노드의 포인터만 조작하면 되기 때문

어떠한 상황이어도 동일한 시간을 가진다.

 

 

 

5️⃣

노드 접근(access) 시 O(n)을 가진다. 보편적인 구현(단방향)의 경우

n번째 노드에 접근을 위해서는 이전 노드를 순회해야 하기 때문

 

 

 

 

 

 

아래는 단일 연결 리스트의 시간 복잡도입니다.

 

단일 연결리스트 연산	real time complexity	assumed time complexity
Access	O(√N * N)	O(n)
Travel	O(√N * N)	O(n)
Insert, Delete	O(1)	O(1)

 

 

 

 

 

Java

 

java로 구현해본 linked list입니다.

 

https://github.com/kma952727/basic-practice/tree/main/src/main/kotlin/structure/linkedlist