자료 구조론 Linked_List (성적표작성)

소개글

컴퓨터과 자료 구조론 직접 작성한 레포트 입니다.

목차

■ 서 론
■ 본 론
■ 결 론

본문내용

■ 서 론
이번 Report로 작성한 단순Linked_List는 프로그래밍을 공부하는 학생이 갖추어야할 가장 기초이며, 기본인 자료구조에 포함되는 하나입니다. 프로그램은 “알고리즘 + 자료구조”로 이루어져 있다고 해도 될 만큼 많은 비중을 차지하고 있으므로, 프로그래밍 공부하는 학생이 자료구조를 공부 안 할 수가 없습니다. 그 만큼 이번 Report는 많은 의미를 가지고 있다고 생각 합니다.
먼저 Linked_List를 알아가기 앞서서 형식상 비슷한 배열과 비교를 하겠습니다.
가장 주요한 점은 배열은 정적메모리 할당이고, Linked_List는 동적메모리 할당입니다. 쉽게 설명하면 정적할당은 생성 시 메모리 크기를 한 번에 할당되어서 더 이상 크기를 늘릴 수 없습니다. 하지만 동적할당은 필요할 때 마다 새로운 공간을 할당 받을 수 있으므로 쉽게 데이터를 저장할 수 있습니다. 또한 정적할당은 메모리 저장 공간을 연속되는 공간에 해야 하지만 동적할당은 그렇게 할 필요도 없으므로 메모리 효율상 좋습니다.
다음으로는 자료의 삽입 / 삭제 가 배열보다 용이 합니다. 배열의 경우 자료를 삽입 / 삭제 할려면 O(n)만큼의 연산 속도가 걸리지만 Linked_List의 경우 O(1)번만 하면 되기 때문에 빠르게 삽입 / 삭제를 할 수 있는 장점이 있습니다.
하지만 많은 장점이 존재 하는 반면에 단점도 존재 합니다. 많은 포인터의 사용으로 저장공간의 낭비가 생기며, 알고리즘이 복잡해집니다. 또한 자료를 검색하는데 있어서 처음부터 찾기 때문에 O(n)만큼의 연산이 필요 합니다. 그러면 Linked_List에 대해서 간단히 알아보겠습니다.
첫 번째, Linked_List 의 노드 형태에 대해 살펴보겠습니다.
위 그림과 같이 Linked_List는 자료부분과 포인터 부분으로 나뉘어 있습니다.
포인터부분에는 다음 노드의 가르키기 위하며 다음 노드의 주소 값을 가지고 있습니다.
위 그림과 같이 Linked_List는 노드와 노드의 연결로 이루어 져 있으며, 첫 번째 노드는 Head노드로서 다음 노드의 주소 값만 가지고 있습니다. 그 주소 값을 따라 가면 1번 데이터가 존재하는 노드를 만날 수 있고 1번 데이터를 가지는 노드에서 주소값을 따라가면 3번 데이터가 가지는 노드 이런 식으로 따라가면 결국엔 19번 데이터를 가지는 노드를 만나게 될 것입니다. 19번 데이터를 가지는 노드는 주소값에 더 이상 연결되어 있는 노드가 없으므로 null 값을 넣음으로 리스트의 끝임을 알리고 있습니다.
두 번째, Linked_List에서 새 노드의 삽입에 대해 알아보겠습니다.

참고 자료

본문 내용 참조