ArrayList(연속리스트) / LinkedList(연결리스트)

노지수·2022년 6월 4일
0

List(리스트)

  • 선형 자료구조다.
  • 순서를 가진 항목들의 모임이다.
  • 배열이 가지고 있는 인덱스라는 장점을 버리고 빈틈없는 데이터 적재라는 새로운 장점을 취한 자료구조이다.
  • 중복된 데이터의 저장을 허용한다.
  • ArrayList, LinkedList등 여러 인터페이스를 구현한 자료형이 있음.
  • JavaScript, Python 같은 경우에는 List를 따로 구현하지 않고 배열에 List의 기능 중 일부를 제공한다.
  • List에서는 인덱스가 중요하지 않고, element간의 순서가 핵심이다.(다른말로 순서라는 의미의 시퀀스(sequence)라고도 한다.)
  • 수학적으로 유한수열을 표현한 것.

List의 기능(operation)

  • 처음과 끝에 데이터 삽입기능
  • 리스트에 데이터가 있는지 체크하는 기능
  • 리스트의 모든 데이터에 접근할 수 있는 기능

연속리스트(ArrayList)

  • 배열을 이용해서 List를 구현한 것을 의미한다.

연속리스트(ArrayList)의 특징

  1. 내부적으로 배열을 이용하기 때문에 접근이 빠르다.(인덱스를 이용하기 때문에 메모리상의 주소를 정확하게 참조하므로 속도가 매우 빠르다.)
  2. 데이터의 추가가 생기면 기본적으로 맨 뒤에 데이터가 추가된다.(특정 인덱스를 선택해 해당 위치에 데이터 추가 가능)
  3. 데이터를 추가하는 과정에서 내부적으로 사용하는 배열이 꽉차면 기존배열 대비 2배 큰 새로운 배열을 만들고 기존의 데이터를 새로운 배열로 복사한다.
  4. 데이터의 추가/삭제가 느리다.(내부적으로 데이터를 배열에 저장 하므로, 배열의 특성상 데이터를 리스트의 처음이나 중간에 저장하면 이후의 데이터들이 한칸씩 뒤로 물러나야 한다.)
  5. 삭제 시 빈자리가 생기면 빈 자리를 채우기 위해서 순차적으로 한칸씩 앞당겨야 한다.
  6. 제네릭 타입을 선언한다면 해당 타입만 추가가 가능하다.

연결리스트(LinkedList)

  • element간의 연결(link)을 통해서 List를 구현할 것을 의미한다.
  • 노드(node)가 사용돈다.
  • head(첫번째 노드)와 tail(마지막 노드)을 가지고 있다.

노드(Node)

  • 노드는 두가지의 정보를 가지는데 첫번째로는 노드의값(data), 두번째로는 다음 노드를 가리키는 참조의 값(next)를 가진다.

연결리스트(LinkedList)의 특징

  • 유연한 메모리공간을 가지고있고, 크기를 선언할 필요가 없다.
  • 데이터를 조회할 때, head부분부터 시작해서 다음노드로 옮겨가며 원하는 데이터까지 탐색한다.(모든 데이터를 순차적으로 조회해야하기 때문에 시간이 상대적으로 오래걸린다. 랜덤액세스가 안된다.)
  • 데이터의 순서를 유지한 채 추가 및 삭제가 빠르다.(배열의 복사나 재할당이 필요없고, 데이터 추가시 새로운노드를 만들고 이전노드와 다음노드의 참조만 바꿔주면 되고, 삭제또한 이전노드와 다음노드를 참조만 연결해주면 되기 때문)

사용할 적절한 상황

  • 데이터를 조회하는 일이 많고, 추가 및 삭제가 적다면 ArrayList가 효율적이다.
  • 추가 및 삭제등 변경이 많은 작업은 LinkedList를 사용하는게 효율적이다.
profile
프로그래밍, 개념 및 이론 기록

0개의 댓글