02-01 리스트 : 링크드 리스트(Linked List)

 

아래의 상기 내용은

"이것이 자료구조+알고리즘이다. With C언어"의 도서 내용과 인터넷의 내용을 실습 및 정리한 글입니다.

1.리스트(List)

 1)정의

 -목록 형태로 이루어진 데이터형식.

 -데이터의 첫번쨰 목록을 헤드(head) 마지막을 테일(tale)이라고 한다.

 

2.리스트와 배열 비교

1)배열

 -데이터가 메모리상에 상의 배치가 연속적.

 -크기가 불변이므로 메모리 낭비가 있다.

 -빠른 접근이 가능

 2)리스트

-데이터가 메모리상에 상의 배치가 비연속적.

-크기가 가변이므로 메모리가 없고 관리가 수월하다.

 -배열보단 느린 접근.

2.링크드 리스트

 1)정의

 -리스트의 한 종류로 연결 리스트라고도 한다.

 -데이터와 데이터 간의 주소(포인터)를 담고 있는 노드를 가지고 있다.

 -각 노드가 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 것이 링크드 리스트.

 

  2)노드(Node) 표현

  

 

 3)링크드 리스트가 가져야할 연산(ADT)

  - 노드 생성(Create Node)/소멸(Destroy Node).

  - 노드 추가(Append Node)

  - 노드 탐색(GetNodeAt)

  - 노드 삭제(RemoveNode)

  - 노드 삽입(InsertAfter, InsertNewHead)