[자료구조 알고리즘] Linked List 개념
https://youtu.be/DzGnME1jIwY
컴퓨터에 자료를 저장하는 구조의 한 종류
일렬로 연결된 데이터를 저장할 때 사용
이렇게 데이터를 저장할 수 있는 공간이 있으면
그 안에 다음 데이터의 주소를 가지고 있는 구조이다.
이렇게
Linked List를 얘기할 때 '배열'하고 비교를 안 할 수가 없다
배열은 배열 방들이 물리적으로 한 곳에 모여 있다.
그래서 배열 방 크기를 한 번 정하면 늘리거나 줄일 수가 없다.
그에 반해서 링크드 리스트는 데이터를 중간에 삽입을 하고 싶으면
앞에 노드가 가지고 있던 주소를 자기가 갖고, 앞에 있는 노드에게는 '너 다음은 나야' 라고 알려주면 된다.
반대로 링크를 빼고 싶을 때는 해당 노드가 갖고 있던 다음 노드의 주소를 앞의 노드에게 주면 된다.
그러면 얘가 링크에서 빠지게 된다.
노드가 Linked List에서는 삭제됐지만 메모리를 여전히 잡아먹고 있는 상태이다.
자바에서는 안 쓰이는 변수들을 알아서 처리해주는데 C나 C++에서는 반드시 안 쓰겠다고 명시를 해주어야 다른 애들이 그 메모리를 쓸 수 있다.
Linked List는 주소를 일일이 찾아다녀야 하기 때문에 붙어 있는 배열보다 속도가 느릴 수가 있다.
삽입하고 삭제하는 것을 배열로 구현해야 한다면 노드가 한 개 추가될 때마다 배열 방을 통째로 다시 선언해서 기존 거를 다 복사하고 하나 추가하고 이런 식으로 해야 되기 때문에 길이가 정해지지 않은 데이터를 핸들링 할 때는 Linked List가 적합하다.
