[Algorithm] Linked List_연결리스트

연결리스트  

1)  정적배열

- 크기 고정  - 메모리가 낭비된다 - 변경에 대처가 어렵다, 유연성이 떨어진다

 

2)  동적 배열

장점 : 실행시간에 heap메모리에 배열을 할당 단점 : 성능 저하 !!          동적으로 증가, 감소는 가능하지만 구현이 어렵고 성능 저하

 

3)  포인터 배열

-  동적인 자료구조 -->  대략의 크기가 정해진 경우        ex) 지뢰찾기 -->  처음설정된 이후에 크기가 변하지 않는 경우            변하더라도 크기가 예측이 가능한 경우 사용     -->  가장 많이 사용되는 대표적인 자료구조     단점 : 데이타의 크기가 예측이 불가능한 경우 사용하기 어려움

 

4) 연결리스트 (linked list)

-  동적으로 데이타를 1씩 생성해나가는 선형자료구조 !!  -  데이타와 데이타를 링크를 통해 순위,순서를 나타낸다 !!   -  노드(node) : 데이타와 링크를 갖는 하나의 블럭  -  링크(link) : 다음 노드를 가르키는 포인터 단점 : 메모리가 연속 되지 않아 탐색 속도 저하

 

*   연결리스트를 사용해야하는 경우
    1) 데이타의 규모가 예측이 불가능한 경우 -->  1~무한대 : 시스템이 허용하는 한계 !!
         ex) editor프로그램 작성  
    2) 중간에서 삽입,삭제가 빈번하게 일어나는 경우 
         ex) 운영체제의 프로세스관리   

연결리스트 구현 방법

 1) 단일 연결리스트  :  다음 노드를가르키는 포인터 1개 존재
  [ 10  ]   [  20  ]   [  30  ]-->데이터
   [ &20 ]-->[  &30 ]-->[      ]--> 링크 :  다음 데이타의 주소값 
    -  방향성 순방향--> 한쪽방향으로만 이동가능

 2) 이중 연결리스트  :  다음노드의 포인터, 이전 노드의 포인터 !! 
 [ 10  ]   [  20  ]   [  30  ]-->데이터
 [ &20 ]-->[  &30 ]-->[      ]--> 링크 :  다음 데이타의 주소값    
 [NULL ]<--[  &10 ]<--[ &20  ]

코드 -> GitHub

github.com/Anchangun/Library/tree/main/C/List

Anchangun/Library