★ 1. 연결 리스트를 이용한 선형 연결 리스트

선형 연결 리스트

선형 연결 리스트에 대해서 살펴보겠습니다.

먼저 연결리스트가 등장하게 된 배경부터 알아봅시다.

선형 리스트를 구현하기 위해서 배열을 사용하였을

경우에 생기는 단점 때문에 연결 리스트가 등장하게

되었습니다.

배열은 구현이 쉽고 인덱스를 이용하여 손쉽게 원소에

접근할 수 있다는 장점이 있지만 연속된 기억 공간에

메모리 할당을 받기 때문에 데이터를 삽입 혹은 삭제를

해야 할 경우 원소들을 이동해야 하므로, 오버헤드가 크고

배열은 선언할 때 할당된 메모리만을 사용할 수 있죠.

그러므로 배열은 여분의 공간까지 생각하여 미리 메모리를

할당해야합니다.

이러한 메모리의 낭비를 없애기 위해서 나온 자료구조가

바로 연결리스트 입니다.

연결 리스트는 여러 개의 작은 공간을 연결하여 하나의 전체

자료구조를 표현하기 때문에 크기 변경이 유연하고

더 효율적으로 메모리를 사용할 수 있습니다.

배열은 연속된 기억공간을 할당받는 반면에

연결 리스트는 프로그램의 실행 중에도 메모리를 할당하기

때문에 메모리의 연속된 공간을 차지하지 못합니다.

그렇기 때문에 생성된 요소를 연결해주는 작업이 필요하죠~~

연결 리스트에 대한 간략?한

설명이였습니다.

다음 포스팅에서 예제를 활용해

코드적인 부분으로 선형리스트 구현을

알아보겠습니다.~