Linked list[c]

○ Structure of Linked listNode 

- Data field[저장할데이터]

- Link field[다른 노드를 가리키는 포인터저장]

- Head pointer : 첫번째 노드를 가르키는 변수마지막 노드링크필드는 NULL[더 이상 연결된 노드없음]

 

○ Array vs Linked list

• Array
  • 배열은 인덱스를 가지고 있기때문에 원하는 데이터에 한번에 접근이 가능 -> 데이터 접근 속도 빠름
  • 배열은 논리적인 순서에 따라서 순차적으로 데이터를 입력하고 물리적 주소도 순차적임
  • 데이터를 삽입,삭제 시에 linked list 처럼 새로운 데이터가 필요할때 마다 동적으로 공간을 못 만듬[새로운 배열을 생성해야됨]
  • 데이터의 삽입, 삭제가 거의 없고 데이터 접근이 많을 겅우 유리함
• Linked list
  • 연결리스트는 배열과 마찬가지로 논리적인 순서에 따라 데이터를 입력하지만 물리적 주소는 순차적이지 않음
  • 공간이 부족할때 마다 새로운 배열을 생성해주어야 되는 배열과 달리 동적으로 공간을 만들수 있[필요한위치에 단순히 node만 추가시키면 됨]
  • 배열처럼 한번에 데이터에 접근하지 않고 연결된 링크를 따라 접근이 가능해서 배열보다 데이터 접근 속도가 느림
  • 데이터의 삽입, 삭제가 용이함

 

○ Create Node

 

○ Connect Node

헤드포인터 head, p는 현재 각각 자신의 노드를 가르키고 있지만 이들을 연결하기 위해서는 

head의 link field를 p를 가리키게하면 연결이 됨

 

○ Insert Node

노드삽입연산은 리스트의 시작이나 끝지점에 노드를 추가를 많이하는데 여기서는 첫번째에 노드를 삽입함

insert라는 Node포인터 구조체함수를 생성하여 새로운 노드를 생성하고 새로운 노드의 link field가 기존의 head가 가리킨 값을 가리키고 head는 새로운노드를 가리킴

 

○ Delete Node

delete라는 Node포인터 구조체함수를 생성해서 Node구조체포인터 deleted가 헤더포인터 head가 가리키는 30을 가리키며 head에는 deleted link field(10)의 값을 저장하여 헤더포인터 head와 첫번째 노드를 완전히 분리시킨다음 deleted를 제거해줌