list.md

List

• 선형적인 자료구조
• 데이터를 일렬로 늘여 놓은 형태
• 순서가 있다

종류

• ArrayList
• LinkedList
  • Single Linked List
  • Double Linked List

ArrayList

• 배열 기반의 리스트
• 메모리 공간을 연속적으로 사용

추가

삽입

삭제

탐색 by index

LinkedList

검색

추가

삽입

삭제

장점

• 배열의 복사나 재할당없이 데이터 추가 가능
• 유연한 공간

단점

• 데이터 접근에 대한 시간이 늘어남

LinkedList VS Array

LinkedList 구현

add(data)

insert(0, data)

delete(data)

DoubleLinkedList

추가

검색 by index

삽입 by index

삭제 by index

[나의 정리]

배열(Array)과 연결리스트(LinkedList)에 대해 알아보자. 배열은 같은 자료형을 가진 변수를 하나로 나타낸 것으로 연속된 메모리 공간으로 이루어져 있다. 따라서 지역성을 갖고 있으며 인덱스를 이용하여 표현하는 특징이 있다. 배열은 인덱스를 통한 검색이 용이(random access)하며 연속적이므로 메모리 관리가 편하다. 하지만 한 데이터를 삭제하더라도 배열은 연속해야 하므로 공간이 남게 되고 이는 메모리 낭비로 이어진다. 또한 배열은 정적이므로 배열의 크기를 컴파일 이전에 정해주어야 한다. 컴파일 이후 배열의 크기를 변동할 수 없다. 반면 연결리스트는 순서가 있는 데이터의 집합이며 불연속적으로 메모리 공간을 차지한다. 동적이기 때문에 고정된 크기를 가지지 않으며 인덱스로 접근하지 않고 포인터를 통한(주소값) 접근을 한다. 리스트는 포인터를 통하여 다음 데이터의 위치를 가리키고 있으므로 삽입과 삭제가 용이하다. 메모리 상에서 연속적이지 않고 동적으로 크기가 정해져 있지 않으므로 낭비되는 부분이 없이 메모리 관리의 편리성이 있다. 하지만 인덱스를 통해 접근하지 않기 때문에 검색 성능이 좋지 않고 포인터를 통해 다음 데이터를 가리키므로 추가적인 메모리 공간이 요구된다.