연결리스트

• 연속적인 메모리에 저장되지 않는 선형 자료구조
• 각각의 노드들이 데이터 필드와 인접한 노드에 참조하기 위한 데이터로 구성
• 배열 VS 연결리스트
  • 배열과 연결리스트 선형으로 데이터를 저장하는 구조
  • 배열
    • 배열은 전체 길이가 고정되어 있고 사전에 길이를 알고 할당 해줘야함
    • 탐색이 빠르다
    • 요소를 삽입,삭제할 때 비용이 많이 듬
      • 중간에 삽입하면 뒤로 나머지를 밀고 삽입
      • 삭제 시 뒤에 있는 것을 모두 당겨야함
  •  연결리스트
    • 전체 길이를 알필요도 없고 사전에 만들어둘 필요가 없음
    • 삽입, 삭제시 용이
      • 삽입 시 해당 위치의 앞,뒤 노드와 연결만 시켜주면 됨
      • 삭제 해당 위치의 앞뒤 노드를 연결 시켜주면 됨
    • 탐색이 느리다
      • 해당 위치에 바로 접근할 수 없어 head부터 순차적으로 접근해서 가야함
• 종류
  • 노드끼리 방향을 어떻게 지정하느냐에 따라 다양함
    • 단방향, 양방향, 원형(head와 tail이 연결) 등등