linked-list
연결 리스트는 배열과는 다르게 메모리에 데이터들이 일렬로 저장되어있지 않아 연결설을 띄지 않지만 연결되어 있는 데이터들의 집합을 의미한다. 아래 그림을 보면 흰상자는 데이터이고 빨간색 상자는 다음 데이터가 있는 주소를 담고 있다. 그리고 value1은 처음에 위치하고 value2는 맨 끝에 있다고 해서 각각 head와 tail이라고 한다. 연결 리스트 자료구조는 조회 할 때 head에서 부터 시작해야한다. 그래서 head를 잃어버리거나 연결을 끊어 버리면 데이터가 날라간다.
연결 리스트와 배열의 메모리 위치
배열과 연결리스트의 시간 복잡도
배열
- 특정 인덱스 값을 불러 올 때 O(1)
- 특정 인덱스에 재할당할 때 O(1)
- 찾고자하는 데이터를 조회, 삭제, 추가할 때는 O(n)
연결 리스트
- 데이터 추가/ 삭제는 O(1)
- 데이터 조회 및 할당은 O(n)
