정의
원소들을 저장할 때 그 다음 원소가 있는 위치를 포함시키는 방식으로 저장하는 자료구조
배열과 연결 리스트는 선형 자료구조라고 불린다
실생활 예시
학교선생님이 영은 현지 재현 상혁 학생을 기억하고싶을때
배열이라면 4칸짜리 배열을 만들고 저장한다
연결리스트 관점에서는 영은이가 현지를 기억하고 현지는 재현 재현은 상혁을 기억하는것
그러면 학교 선생님은 영은만 기억해도 된다
성질
1 k번째 원소를 확인/변경하기 위해 o(k)가 필요함
그림에서 72를 찾기 위해서는 3에서 13 13에서 72까지 가야한다
이렇게 가지 않고서는 72가 대 체 어디있는지 알 수 가없다
배열과 다르게 공간에서 어디에 위치하여있는지를 알 수 없기 때문
임의의 위치에 원소를 추가/임의 위치 원소 제거는 o(1)
원소들이 메모리 상에 연속해있지 않아 Cache hit rate가 낮지만 할당이 다소 쉬움
종류
단일 연결 리스트
각 원소가 자신의 다음 원소의 주소를 들고 있는 연결 리스트
이중 연결 리스트
이전 원소와 다음원소의 주소를 둘 다 들고있어요
원소가 가지고 있어야 하는 주소가 1개 더 있으니 메모리 사용이 더 크다
원형 연결 리스트
끝이 처음과 연결되ㅓ어있음
기능과 구현
임의의 위치에 원소를 추가 o(1)
임의의 위치에 원소를 추가하려하면 배열같은 경우에는 원소를 추가한뒤 그 뒤에 원소들을 한칸씩 밀어야하지만, 연결 리스트는 임의의 위치가 기억하는 주소값을 알고있다면 그 주소값만 서로 바꿔주면 된다.
임의의 위치의 원소를 알지 못한다면 원소의 처음값부터 찾아가야 하기 때문에 o(n)이 된다.
임의의 위치의 원소를 제거 o(1)
정리
임의의 위치에 있는 원소를 확인/변경 = o(n)
임의의 위치에 원소를 추가/임의의 위치의 원소 제거 = o(1)
주로 메모장 같은 곳에 사용함
커서가 가르키는 위치에 글자를 추가하거나 지우는 명령을 수행해야함
배열은 글자를 추가하거나 제거할때 비 효율적이지만 연결리스트는 o(1)이기 때문에 좀 더 효율적
참고 자료
