List

리스트

순서를 가진 데이터 집합을 가리키는 추상자료형 (abstract data type) 으로, 동일한 데이터를 가지고 있어도 상관 없다. 리스트는 크게 두가지로 나뉘는데, 순차 리스트와 연결 리스트가 있다.

🤦🏻‍♀️ 순차 리스트 : 배열을 기반으로 구현된 리스트
     연결 리스트 : 메모리의 동적할당을 기반으로 구현된 리스트

 

구현 방법

1. 1차원 배열에 항복들을 순서대로 저장한다
2. 데이터의 종류와 구조에 따라 구조화된 자료구조를 만들어 배열에 저장할 수도 있다

int [] L = {4,5,9,11 };

 

데이터 접근 방법

배열의 인덱스를 이용해 원하는 위치의 데이터에 접근할 수 있다

int a = L [1]; //L =5

삽입 연산

삽입 위치 다음의 항목들을 뒤로 이동해야 한다

삭제 연산

삭제 위치 다음 항목들을 앞으로 이동해야 한다

문제점

1. 단순 배열을 이용한 순차리스트를 구현해 사용하는 경우, 자료의 삽입/ 삭제 연산 과정에서 연속적인 메모리 배열을 위해 원소들을 이동시키는 작업이 필요하다
2. 원소의 개수가 많고, 삽입/삭제 연산이 많이 일어나면 작업 시간이 크게 증가한다
3. 배열의 크기가 정해져 있으면, 실제로 사용될 메모리보다 크게 할당하여 메로리 낭비가 발생하고, 반대로 더 작게 정해져있다면 다시 배열을 복사하고 만드는 작업을 해야한다

따라서, 이런 문제점을 발생시키지 않기 위해 연결 리스트 (Linked List) 를 활용해야 한다

연결 리스트

특성

1. 자료의 논리적인 순서와 메모리 상의 물리적인 순서가 일치하지 않고, 개별적으로 위치하고 있는 각 원소를 연결하여 하나의 전체적인 자료 구조를 이룬다
2. 링크(참조값)를 통해 원소에 접근하므로, 순차 리스트에서처럼 물리적인 순설르 맞추기 위한 작업이필요 없다
3. 자료구조의 크기를 동적으로 조정할 수 있어서 메모리의 사용이 효율적이다

기본 구조

<1> 노드

연결 리스트에서 하나의 원소를 표현하는 building block

1. 데이터 필드 :원소값 저장 (원소의 종류나 크기에 따라 구조를 정의하여 사용함)
2. 링크필드 : 다음 노드의 참조값 저장

<2> 헤드

연결 리스트의 첫 노드에 대한 참조값을 갖고 있음

🧸Tail 이 없으면 ,마지막 요소를 찾기 위해서는 Head 부터 iterate 둬야 함. 따라서 tail 을 더해서 관리할 수도 있다.

<1> 단순 연결리스트

Singly Linked List

연결 구조

링크를 한개만 유지하는 리스트

1. 헤드가 가장 앞의 노드를 가리키고, 링크필드가 연속적으로 다음 노드를 가리킨다
2. 링크가 null 인 노드가 연결리스트의 가장 마지막 노드이다

삽입

Case 1: Empty

공백 리스트에 'A' 를 추가할 때

Case 2: !Empty

1. 첫번째에 삽입 'A' 를 원소로 갖고 있는 리스트의 첫번째에 'C' 노드를 삽입할 때

   2. 마지막에 삽입 'C', 'A'를 원소로 갖고 있는 리스트의 마지막에 'D' 노드를 삽입할 때

   3. 중간에 삽입할 때 'C', 'A', 'D' 를 원소로 갖고 있는 리스트의 두번째에 'B' 노드를 삽입할 때

삭제

Case 1: 중간의 원소 삭제 'A' , 'B', 'C', 'D' 를 원소로 갖고 있는 리스트의 'B' 노드를 삭제할 때

Case 2: 삭제하려는 노드의 앞이 head 일 경우 'C', 'A', 'D' 를 가지고 있ㄴ는 리스트의 'C'를 삭제할 때

장단점

1. 장점 : 관리할 링크가 하나밖에 없기 때문에 상대적으로 관리가 쉽다
2. 단점 : 삭제 시 삭제하려는 노드의 이전 노드를 다음 노드의 참조값을 가리키도록 수정해야함