Linked List
정의
링크드 리스트(Linked List)는 노드(자료)들이 한 줄로 연결되어있는 방식으로 데이터를 저장하는 자료구조이다. 각 노드는 데이터와 포인터를 가지고 있다. 포인터는 다음 혹은 이전의 노드와의 연결을 담당한다. 자동적으로 길이가 늘어나는 배열이라고 생각할 수 있겠는데, 사실 지금 공부하고 있는 자바스크립트에서는 큰 의미가 없지 않나 싶다. 자바스크립트에서는 배열의 길이를 정해주지 않아도(메모리르 미리 할당하지 않아도) 데이터를 넣고 빼는데 문제가 없다. 반면 C언어에서는 메모리를 미리 할당해주지 않으면 문제가 생기는데, 링크드 리스트를 사용하면 편할 것 같다.
링크드 리스트의 종류
단일 연결 리스트
각 노드들에 데이터와 포인터가 있고, 포인터는 다음 노드를 가리킨다.
이중 연결 리스트
각 노드들에 데이터와 두개의 포인터가 있고, 포인터 각각이 이전과 다음 노드를 가리킨다.
원형 연결 리스트
마지막 노드의 포인터가 맨 처음 노드를 가리킨다. 일반적인 단일 연결 리스트의 마지막 노드의 포인터를 처음 노드와 연결
배열 리스트와 링크드 리스트의 차이
배열 리스트의 경우 메모리를 미리 할당해놓기 때문에 메모리 낭비가 있지만, 링크드 리스트는 동적으로 메모리를 할당하기 때문에 메모리 낭비를 줄일 수 있다. 하지만 무조건 링크드 리스트가 배열보다 좋은 것은 아니다. 링크드 리스트는 리스트의 중간에 데이터를 추가하거나 삭제할 때 O(1)의 시간이 걸린다는 장점이 있지만, 특정 데이터의 위치를 검색하는 데에는 배열과는 다르게 O(n)의 시간이 걸린다는 단점도 있다.(나중에 비교 표 만들기)
구성
리스트의 구성
리스트에 노드를 추가하는 insert(value)
앞 -> 뒤 에서 앞 -> N -> 뒤 로
1. 새로운 노드(N)를 생성하고, 데이터(value)를 할당한다.
2. N의 포인터가 뒷 노드를 가리키게 한다
3. 앞 노드의 포인터가 N노드를 가리키게 한다
리스트에서 특정 노드를 제거하는 remove(삭될 노드의 position)
앞 -> N -> 뒤 에서 앞 -> 뒤 로
1. 앞 노드의 포인터를 뒤 노드를 가리키게 한다
2. N이 차지하고 있는 메모리를 비워준다
init()
특정 값의 위치를 찾는 search()
특정 위치의 데이터를 변경하는 modify()
head를 가리키는 노드 포인터
