[CS] 지식 - 3 (자료구조_List)

List

List

의미 및 특징

• 순서를 가진 데이터의 집합을 가리키는 추상자료형
• 데이터 중복 허용분류
• 순차 리스트, ArrayList
  • 배열을 기반으로 구현된 리스트
• 연결 리스트, LinkedList
  • 메모리의 동적할당을 기반으로 구현된 리스트

순차 리스트, ArrayList

• 의미 및 특징
  • 1차원 배열에 항목들을 순서대로 저장
  • 배열의 인덱스를 이용해 데이터 접근 가능
• 삽입 연산
  • 데이터 삽입 시, 삽입되는 인덱스 이후의 데이터가 한 칸씩 밀리는 방식
• 삭제 연산
  • 데이터 삭제 시, 삭제되는 인덱스 이후의 데이터가 한 칸씩 땡겨지는 방식
• 단점
  • 데이터 삽입, 삭제 시 메모리 배열을 위해 리소스가 많이 소모됨.

연결 리스트, LinkedList

의미 및 특징

• 논리적인 순서와 메모리 상의 물리적인 순서가 일치하지 않고, 개별적으로 위치하고 있는 각 원소가 하나의 전체적인 자료구조를 이룸.
• 자료구조 크기를 동적으로 조절할 수 있음(메모리를 효율적으로 사용할 수 있음)

  노드, Node

• LinkedList에서 하나의 원소를 표현하는 키워드
• 데이터 필드와 링크 필드로 구성되어 있음
  • 데이터 필드 : 값을 저장
  • 링크 필드 : 다음 노드의 참조값을 저장

    헤드, Head

• 연결 리스트의 첫 노드에 대한 참조값을 갖고 있음
• 가장 첫 노드의 주소를 의미하는 듯함

연결 리스트의 종류

• 단순 연결 리스트(단방향)
• 이중 연결 리스트(양방향)
• 원형 연결 리스트단순 연결 리스트
• 연결 구조
  • 헤드 : 첫 노드의 주소값을 참조
  • 노드 : 다음 노드의 링크 필드에 주소값을 저장
  • 마지막 노드 : 링크 필드에 null