List 리스트

* List?

순서를 가진 데이터의 집합을 가리키는 추상자료형(abstract data type)

동일한 데이터를 가지고 있어도 상관 없다. (원소 중복 허용)

 

구현 방법에 따라서 

 

1) 순차리스트ArrayList: 배열을 기반으로 구현된 리스트. 원소의 물리적 저장 순서와 원소의 논리적 순서가 같다.

2) 연결리스트Linked List: 메모리의 동적 할당(객체 생성)을 기반으로 구현된 리스트. 원소의 물리적 저장 순서와 원소의 논리적 순서는 다르다. 원소 하나하나를 객체로 만들어서 연결하는 자료구조

 

 

1. 순차 리스트(Array List)

구현 방법: 1차원 배열에 항목들을 순서대로 저장한다. 데이터의 종류와 구조에 따라 구조화된 자료 구조를 만들어 배열로 사용할 수도 있다. 데이터의 접근은 배열의 인덱스를 사용하여 원하는 위치의 데이터에 접근할 수 있어서 편리하다. 그러나 단점은 원소의 삽입/삭제 연산이 있을 경우 그 원소가 들어갈 공간을 마련하기 위해서 기존의 원소들의 위치를 전부 움직여야 하는 단점이 있다. 따라서 원소의 개수가 많고 삽입/삭제 연산이 빈번하게 일어날수록 작업에 소요되는 시간이 크게 증가한다. 배열의 크기가 정해져 있는 경우, 실제로 사용될 메모리보다 크게 할당하여 메모리의 낭비를 초래할 수도 있고, 반대로 할당된 메모리보다 많은 자료를 사용하여 새롭게 배열을 만들어 작업을 해야하는 경우가 발생할 수도 있다. 

 

2. 연결 리스트(Linked List)

자료의 논리적인 순서와 메모리 상의 물리적인 순서가 일치하지 않고, 개별적(객체)으로 위치하고 있는 원소의 레퍼런스를 연결하여 하나의 전체적인 자료구조를 이룬다. 

링크를 통해 원소에 접근하므로, 순차 리스트에서처럼 물리적인 순서를 맞추기 위한 작업이 필요하지 않다. 

자료구조의 크기를 동적으로 조정할 수 있어서, 메모리의 효율적인 사용이 가능하다.  

 

* Node

연결 리스트에서 하나의 원소에 필요한 데이터를 갖고 있는 자료단위

구성 요소로는 1) 데이터 필드(원소의 값을 저장하는 자료 구조. 저장할 원소의 종류나 크기에 따라 구조를 정의하여 사용한다.) 2) 링크 필드(다음 노드의 주소를 저장하는 자료 구조)

 

* Head

리스트의 처음 노드를 가리키는 레퍼런스서를 가진 데이터의 집합을 가리키는 추상자료형(abstract data type) 헤드는 데이터필드가 없고 링크필드만 있다. 

 

연결 구조

노드가 하나의 링크필드에 의해 다음 노드와 연결되는 구조를 가진다. 

헤드가 가정 앞의 노드를 가리키고, 링크 필드가 연속적으로 다음 노드를 가리킨다. 

최정적으로 NULL을 가리키는 노드가 리스트의 가장 마지막 노드이다.