데이터구조 11차시: 선형리스트( Singly Linked List)의 구현

선형리스트의 구현

ㅇ 선형리스트는 배열을 이용하면 쉽게 구현이 가능하지만,

  - 배열이 가지는 한계 때문에 부적절

ㅇ 배열의 단점

  - 미리 정해진 크기를 넘어갈 경우 변경이 쉽지 않다.

  - 공간 낭비가 발생할 수 있다.

  - 중간에 새로운 요소를 넣기가 어렵다.

ㅇ 배열의 단점은 Singly linked list (SLL)로 보완

  - 데이터의 크기를 미리 알 수 없어도 사용가능

  - 공간 낭비가 없다.

  - 중간에 새로운 요소 삽입이 쉽다.  

ㅇ SLL의 구조

  - 개별 노드들을 줄로 이은 형태

  - 필요할 때마다 새로운 노드를 추가

  - 중간의 노드를 삭제하려면, 노드 제거후 줄 잇기만 다시 하면 ok

ㅇ SLL 노드의 구현

  - self-referencing structure를 이용

  - 예를 들어, 정수를 저장하는 SLL를 만들 경우,

  - 노드의 C언어 정의는

struct node {    int n;    struct node *next }

ㅇ 비디오 

  - Singly Linked List의 구현 전반에 대해서 설명합니다.