몽상실현개발주의

[종만북] 연결 리스트 / 선형 자료 구조 연결 리스트 배열의 원소들의 순서를 유지하면서 임의의 위치에 원소를 삽입하거나, 임의의 위치에서 원소를 삭제하는것은 시간이 오래 걸리는 작업이다. 해당 위치 뒤에 있는 원소들을 하나씩 뒤칸 혹은 앞칸으로 옮겨야 하기 때문이다. 정확한 수행시간은 삽입이나 삭제 위치에 따라 다르지만, 평균적인 경우 이 작업들에는 원소들의 개수에 선형 비례하는 시간이 소요된다. 이와 같은 문제를 해결하기 위해 고안된 자료구조가 연결 리스트(Linked List) 이다. 연결 리스트는 특정 위치에서의 삽입과 삭제를 상수 시간에 할 수 있게 해 준다. 배열에서는 메모리의 연속된 위치에 각 원소들이 저장되어 있지만, 연결 리스트는 원소들이 메모리 여기저기 흩어져 있고 각 원소들은 이전과 ..