Linked List

💡 Linked List

Linked List는 Node라는 구조체로 이루어져 있는데,
Node는 데이터 값과 다음 Node의 address를 저장합니다
Linkde List는 물리적인 메모리상에서는 비연속적인 저장이 되지만
Linked List를 구성하는 각각의 Node의 address를 가리킴으로써
논리적인 연속성을 가진 자료구조이다

Linked List는 tree, graph등 다른 자료구조를 구현할 때 자주 쓰이는 자료구조이다

Linked list를 설명할 때에는 이러한 장점들을 설명하면 좋다

1. 메모리상에서 불연속적으로 데이터가 저장된다는 점

2. Node의 next address를 통해 불연속적인 데이터를 연결하여
   논리적 연속성을 보장한다는 점

3. 데이터가 추가 되는 시점에서 메모리를 할당하기 때문에
   메모리 효율이 좋다는 점

---

Linked list 구조

lined list는 Array와 달리 메모리에 할당되는 경우에

연속성을 갖고 있지 않다 즉 뒤죽박죽의 저장 순서를 갖고 있다

해당 그림의 data들도 linked list의 특성을 갖고 있기 때문에

메모리 상의 저장 순서는 뒤죽박줄일 것이다

그러나 linked list의 특징이 여기서 더 나타나는데

1번째 Data의 주소값은 500번을 갖고 있지만 next address 는 1004번을 향한다
(추가로 1번째 Data는 Head라고 부른다)

즉 저장된 공간은 서로 다르지만 1번째 Data와 2번째 Data는 연결되어 있는것 이다

여기서 봐야 할 점은 마지막 Node의 next address는 NULL 값을 지닌다는 것 이다

이것이 논리적 연속성이다

💡 논리적 연속성

각 Node들은 Next Address 정보를 갖고 있기 때문에
논리적으로 연속성을 유지하면서 연결되어 있다
Array의 경우 연속성을 유지하기 위해 물리적 메모리 상에서
순차적으로 저장하 는 방법을 채택하고
Linked list에서는 메모리에서 연속성을 유지하지 않아도 되기 때문에
메모리 사용이 좀 더 자유로운 대신, Next Address를 추가적으로 저장해야 하기 때문에
데이터 하나당 차지하는 메모리가 더 커지게 된다

---

Linked list operation

왼쪽 정렬	가운데 정렬
access	O(n)
search	O(n)
insertion	O(1)
deletion	O(1)

그림에서와 같이 B와 C사이에 E데이터를 삽입하는 경우에

B의 Next Address ➡ E의 Address

E의 Next Address ➡ C의 Address

Array와 달리 Next Address만 할당해주는걸로 중간 삽입을 완료할 수 있다

delete는 반대로 할당하면 된다 만약 E를 삭제하고 싶다면

B의 Next Address ➡ C의 Address 로 설정하면 끝이다

설명에서와 같이 Linked list의 append delete의 시간 복잡도는 O(1)이다

Array의 O(n)의 시간보다 빠른 속도라는 것을 알 수 있다

반면에 linked list의 access는 O(n)의 시간복잡도가 할당된다

Array에서는 random access가 지원이 되지만 linked access는 순차적 접근밖에 허용이 되지 않기 때문이다

search 또한 마찬가지이다