자료구조: ch5) 연결 리스트(Linked list)

연결리스트?

• 포인터를 이용해 구현된 리스트

• 배열은 순차적 연결된 공간에 데이터를 나열. but 링크드 리스트는 떨어진 곳에 존재하는 데이터를 연결하는 구조

• 노드: 데이터 저장 단위로 구성
  포인터: 각 노드 안에서, 다음이나 이전의 노드와의 연결 정보를 가진 공간.

  

한 방향 연결리스트 삽입/삭제 연산

• 신창수 교수님의 유튜브 강의 캡쳐 (삽입/삭제)
  

연결리스트 장/단점

장점 :
-데이터 공간을 미리 할당하지 않아도 됨.
-삽입이 간단. 항목 생성후 포인터 값만 변경해주면 됨.

단점 :
-연결을 위한 별도 데이터 공간이 필요함 (참조 포인터를 위한 메모리 공간 낭비) -> 저장공간 효율이 높지 않다
-중간 데이터 삭제 시, 앞-뒤 데이터를 재연결해야 함.
-연결 정보를 찾는 시간이 필요->접근속도가 느려질 수 있음. (첫 항목부터 순차적 접근하므로 최대 O(n) 시간 소요)

->참조는 배열이 간단 / 삽입은 연결리스트가 간단.