Back to the Basics

단일 연결 리스트 자료구조 연결 리스트는 실행 시간에 메모리를 할당하거나 해제할 수 있는 동적 자료구조이다. 이번 포스팅에서는 단일 연결 리스트의 개념과 단일 연결 리스트 연산들의 구현에 대해 간단하게 정리해 보았다. 참고로 사용한 언어는 python이다. 1. 연결 리스트의 개념 연결 리스트 자료구조는 배열처럼 선형 자료구조에 속하지만 인덱스로 접근하는 것이 아닌, 각 노드가 다음 노드에 대한 참조를 갖는 구조이다. 배열처럼 자료들의 메모리가 선형적으로 저장되지 않고 흩어져(?) 있지만 각 노드의 참조를 갖고 있기 때문에, 그 참조를 따라 다음 노드로 접근할 수 있다. 아래의 그림을 보면 쉽게 이해할 수 있다. 각 노드는 데이터를 담는 data field와 다음 노드를 참조하는 pointer field..

삭제 연산 동작 길이가 5인 리스트에서 index 1에 있는 요소를 지우고 싶은 경우 인덱스 1 뒤에 있는 데이터를 모두 한 칸씩 앞으로 밀어서 저장한다. 인덱스 1에 인덱스 2에 있는 요소를 저장한다 인덱스 2에 인덱스 3에 있는 요소를 저장한다 인덱스 3에 인덱스 4에 있는 요소를 저장한다 동적 배열에서 접근할 수 있는 인덱스 범위도 1을 줄여준다동적 배열은 배열의 크기와 개발자가 사용하는 인덱스들의 범위를 따로 관리한다. 삭제 연산 시간 복잡도 삭제 연산도 아무 위치에 있는 데이터를 삭제할 때와 맨 뒤 데이터를 삭제할 때, 두 경우도 나눠서 생각할 수 있다. 최악의 경우 : 맨 앞의 데이터를 지울 때 삭제 연산은 최악의 경우 삭제할 데이터가 맨 앞에 있는 경우이다. 인덱스 1부터 끝까지 모든 요소들..