[자료구조 연결 리스트] What is Linked List? / 연결 리스트란?

※ malloc()과 free()를 기반으로 하는 메모리 동적 할당에 완전한 이해가 선행되어야 한다

 

연결 리스트(Linked List)에 대해 알아보자

 

연결 리스트(Linked List)

    - 배열 형태의 자료구조에서 더 발전된 개념으로 각각의 자료가 존재하고 그들을 특정 링크로 연결하는 것을 뜻한다

 

출처) 윤성우의 열혈 자료구조

   

연결 리스트 구현

    - 위에 언급한 바구니 하나를 노드(Node)라고 표현하고 노드는 다음과 같이 구성된다

 

출처) fundamentals of data structures in c - horowitz

    - link에 다음으로 이어질 노드의 주소값을 삽입함으로써 노드끼리 순차적으로 연결한다

 

    - 노드를 삽입할 때는 2가지의 경우가 존재한다

        - 1. 연결 리스트의 가장 앞에 노드를 삽입하는 경우

출처) 경북대학교 정기숙 교수님 자료구조 강의자료

        - 2. 연결 리스트의 노드와 노드 사이에 삽입하는 경우

출처) 경북대학교 정기숙 교수님 자료구조 강의자료

    - 노드를 삭제할 때 또한 2가지의 경우가 존재한다

        - 1. 삭제할 노드가 연결 리스트의 가장 마지막 노드인 경우

출처) 경북대학교 정기숙 교수님 자료구조 강의자료

        - 2. 삭제할 노드가 연결 리스트의 노드와 노드 사이에 존재하는 경우

출처) 경북대학교 정기숙 교수님 자료구조 강의자료