C언어 리스트, 연결리스트

리스트(List)

• 순서를 가진 data들의 모임(Ex: 사야할 물건 항목, 요일, 한글 자음의 모음, 카드 한벌의 모음)

리스트 구현 방법

1. 배열 : 구현 간단, 삽입 삭제 오버헤드 있음, 항목의 개수 제한(크기 고정)
2. 연결 리스트(포인터) : 구현 복잡, 삽입 삭제 효율적, 크기가 제한 없음
   

배열로 구현된 리스트의 개념

• 배열은 항목(data)을 저장할 수 있는 여러개의 공간을 가짐
• 배열로 구현된 리스트에서 삽입과 삭제
  

-리스트 구현
element : 배열에 저장되는 항목(data), 즉 데이터타입, element item
list : 1차원 배열
length : 배열에 저장된 항목들의 개수

연결 리스트(linked list)

순차적 표현 : 배열 리스트
비순차적 표현 : 연결 리스트

노드(node)

데이터를 저장하는 부분과 다음 노드를 가리키는 포인터로 구성됨

연결리스트 특징

• 동적으로 크기가 변할 수 있고, 삭제나 사입 시에 데이터를 이동할 필요가 없는 리스트
• 리스트의 항목들을 노드라는 형태로 분산하여 저장
  데이터가 메모리상에 흩어져서 존재
  순서를 유지하기 위해 앞에 데이터를 가르키는 줄(링크)를 가짐
  메모리안에서 노드의 물리적인 순서(저장위치) 논리적 순서(리스트상 데이터순서)와 상관없음
  
• 노드
  데이터 필드 : 데이터, 항목
  링크 필드 : 다음 항목을 가르키는 주소, 주소값, 포인터

• 헤드 포인터
  첫 번째 노드를 가르키고 있는 포인터 변수가 필요
  
  
• 연결리스트(노드)의 장단점
  장점
  노드들의 순서가 리스트상의 순서와 동일하지 않아도 됨
  연속적인 기억공간 필요x
  미리 기억공간을 확보할 필요x 단점
  링크 필드를 위한 추가 데이터 공간 필요
  구현과 방법이 배열에 비해 복잡하고 에러 발생 가능성이 높음
  
  

연결 리스트의 시작(시작 주소)

• 첫 번째 원소를 (시작을) 가리키는 포인터

• 새로운 리스트는 초기에는 비어있는 상태이므로 0으로 초기화됨
  

• 새로운 노드의 생성
  new_nod = (listPointer)malloc(sizeof(listNode));//malloc 한 노드는 계속 메모리에 존재함!
  

• 새로운 노드의 삽입
  새로운 노드를 삽입할 경우 first가 가리키고 있는 것이 NULL일 경우와 그렇지 않을 경우로 나뉨
  first는 리스트의 시작!