리스트

리스트란 무엇인가

자료를 순서를 가지고 저장하는 자료구조이다.

배열과 다른 점?

예를 들어 중간의 파일이 하나 삭제 되었다고 해보자.
이때 배열과 리스트의 처리 방식이 다르다.

이와 같이 배열같은 경우는 그 인덱스의 값이 사라지는 것에 반해
리스트는 지우고 그 밑의 원소들을 한 칸식 올려 빈 칸이 없이 만든다.
삭제뿐만이 아니라 생성도 마찬가지이다.

추상 자료형

이름	입력	출력	설명
리스트 생성	최대 원소 개수 n	리스트 l	최대 n개의 원소를 가지는 공백의 리스트 l 생성
리스트 삭제	리스트 l	N/A	리스트의 모든 원소 삭제
가득 찼나	리스트 l	True/False	리스트의 원소 개수가 최대 원소 개수와 같은 지를 반환
원소 추가	리스트 l 원소위치 p 원소 e	성공 · 실패 여부	원소 e를 리스트의 특정 위치 p에 추가
원소 제거	리스트 l 원소위치 p	성공 · 실패 여부	리스트의p에 있는 원소 제거
초기화	리스트 l	N/A	리스트의 모든 원소를 제거
원소 갯수	리스트 l	원소의 개수	리스트의 원소 갯수를 반환
원소 반환	리스트 l 원소위치 p	원소	리스트에서 위치p에 있는 원소를 반환

리스트의 종류

배열 리스트

• 배열을 이용한 리스트
• 논리적 (저장) 순서와 물리적 (저장) 순서가 동일하다.
• 원소의 위치 인덱스가 배열과 같이 0부터 시작한다
• 배열과 다르게 모든 자료가 일직선으로 연결되어 있어야 한다. (중간에 자료가 끊기면 안 된다.)
• 삽입 · 제거
  • 삽입
    넣고 싶은 인덱스부터 기존 원소들을 한 칸씩 뒤로 이동하는 연산이 필요하다.
  • 제거
    빼고 싶은 인덱스부터 기존 원소들을 한 칸씩 뒤로 이동하는 연산이 필요하다.
    

단점

시간복잡도가 O(n)이 되기에 원소가 많이 질 수록 느려짐

연결 리스트

• 연결 포인터를 이용하여 구현한다.
• 배열 리스트와 달리 논리적 (저장) 위치만 순차적이고, 물리적 (저장) 위치는 순차적이지 않을 수 있다.
• 자료(Data) + 링크(Link)로 만들어진 노드로 이루어져있다.
  • Data는 실제 자료가 들어가고
  • Link는 다름 노트의 주소가 있다.
• 추가와 제거
  • 추가
    기존 연결되어 있는 링크를 제거한 후 새로운 노트에 링크를 연결 하고 새로운 노트의 링크를 기존 연결되어있던 노트에 연결한다.
  • 제거
    제거할 노드에 연결되어있는 링크를 제거하고 제거할 노드가 가주고 있던 노드에 연결한다.
    

파생

• 단순 연결 리스트(Singly Linked List)
• 원형 연결 리스트(Circular Linked List)
  • 순환 구조
• 이중 연결 리스트(Double Linked List)
  • 노드들이 양방향으로 연결되어 있음
    • 장점: 이전 노드에 바로 접근이 가능하다.
    • 단점: 이전 링크를 추가하기 때문에 메모리가 추가적으로 필요하다.