알고리즘 2주차 - 선형리스트

Keywords : 메모리, 연결 리스트, 순차 리스트

 

메모리 동작 방법

• 저장 : 컴퓨터에 공간 요청해 주소 받음, 여러 개 저장 시, 순차 / 연결 리스트 중 하나의 방법 사용해야 (각 장단점 알아야)
• 주소 : 바이트 단위로 위치 식별하는 물리적 주소값, 64kb = 60 * 1024 byte = 65536 byte
• 변수 선언 : 메모리 공간 할당, 이후에는 변수명으로 메모리 공간을 대신 사용

선형 리스트

• 순차 리스트
  • 원소를 논리적인 순서대로 메모리에 연속하여 저장
  • 삽입 : 빈 자리 생성 (나머지 원소 한 자리씩 뒤로 이동) => 빈 자리에 삽입
  • 삭제 : 원소 삭제 => 빈 자리 채우기 (나머지 원소 한 자리 씩 앞으로 이동)
  • 장점 : 특정한 원소가 필요할 때 편리 (특정 원소의 위치 바로 계산 가능)
  • 문제점 : 
    • 연산에 추가 작업 및 시간 소요 (오버헤드 발생하여 데이터 많아지면 성능 저하 문제)
    • 비효율적인 메모리 사용
• 연결 리스트
  • 각 원소에 다음 원소의 주소 저장 (Data, Link)
  • 자료의 논리적인 순서와 물리적인 순서가 불일치
  • 장점 :
    • 원소 추가, 삭제 과정 편리, (이어진 주소의 배열을 만들거나 추가로 원소 이동하지 않아도 됨)
    • 물리적인 순서 맞추기 위한 오버헤드 발생하지 않음
    • 크기 변경 유연
    • 효율적인 메모리 사용
• 인덱스 : 원소의 위치로, 0부터 시작