[List 자료구조] Array List, Linked List

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

 

1) List의 특성

    1. 동일한 데이터를 가지고 있어도 상관 없음

    2. 구현 방법에 따라 크게 두 가지로 나뉨

        * 순차 List : 배열을 기반으로 구현된 List

        * 연결 List : 메모리의 동적할당을 기반으로 구현된 List

 

2) List의 주요 함수

• addtoFirst() : List의 앞쪽에 원소를 추가하는 연산
• addtoLast() : List의 뒤쪽에 원소를 추가하는 연산
• add() : List의 특정 위치에 원소를 추가하는 연산
• delete() : List의 특정 위치에 원소를 삭제하는 연산
• get() : List의 특정 위치에 있는 원소를 리턴하는 연산

3) 순차 List (Array List)

구현 방법

1. 1차원 배열에 항목들을 순서대로 저장

2. 데이터의 종류와 구조에 따라 구조화된 자료구조를 만들어 배열로 구현할 수도 있음 

    예) List = {5,10,15,20}  

데이터 접근

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

    예) 3에 위치한 자료 

    int a = List[3];  // List[3] = 20

 

 

삽입 연산

삽입 위치 다음의 항목들을 이동해야 함

    예) 2의 위치에 12 삽입

삭제 연산

삭제 위치 다음의 항목들을 이동해야 함

    예) 1의 위치에서 10 삭제

단순 배열을 이용한 순차 List 구현의 단점 

1. 자료의 삽입/삭제 연산 과정에서 연속적인 메모리 배열을 위해 원소들을 이동시키는 작업이 필요함

2. 원소의 개수가 많고 삽입/삭제 연산이 빈번하게 일어날수록 작업에 소요되는 시간이 크게 증가

3. 배열의 크기가 정해져 있는 경우, 실제로 사용될 메모리보다 크게 할당하여 메모리의 낭비를 초래할 수도 있고, 반대로 할당된 메모리보다 많은 자료를 사용하여 새롭게 배열을 만들어 작업을 해야 하는 경우가 발생할 수도 있음

 

4) 연결 List (Linked List)

단순 배열을 이용한 순차 List의 단점을 보완한 자료구조

 

    1. 자료의 논리적인 순서와 메모리 상의 물리적인 순서가 일치하지 않고, 개별적으로 위치하고 있는 원소의 주소를 연결하여 하나의 전체적인 자료구조를 이룸

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

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

    4. 단점 : 구현이 배열 List보다 복잡

 

노드 : 연결 List에서 하나의 원소에 필요한 데이터를 갖고 있는 자료 단위

• 데이터 필드 : 원소의 값을 저장하는 자료 구조, 저장할 원소의 종류나 크기에 따라 구조를 정의하여 사용함
• 링크 필드 : 다음 노드의 주소를 저장하는 자료 구조

헤드 : List의 처음 노드를 가리키는 자료 구조

단순 연결 List 

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

- 헤드가 가장 앞의 노드를 가리키고, 링크 필드가 연속적으로 다음 노드를 가리킴

- 최종적으로 Null을 가리키는 노드가 List의 가장 마지막 노드임

Single Linked List

단순 연결 리스트의 삽입 연산

•  'A', 'C', 'D' 원소를 갖고 있는 리스트의 두 번째에 B노드를 삽입

    1. 메모리를 할당하여 새로운 노드 new 생성 

    2. 새로운 노드 new의 데이터 필드에 데이터 'B' 저장

    3. 삽입될 위치의 바로 앞에 위치한 노드의 링크 필드를 new에 복사

    4. new의 주소를 앞 노드의 링크 필드에 저장

삽입하는 new 노드 0x1020

• List의 처음 위치에 노드를 삽입하는 알고리즘

addtoFirst(L, i)			// List 포인터 L, 원소 i
	new <- createNode();		// 새로운 노드 생성
    new.data =i;			// 데이터 필드 작성
    new.link = L;			// 링크 필드 작성
    L = new;				// List의 처음으로 지정
end addtoFirst()

 

• List의 마지막에 노드를 삽입하는 알고리즘

addtoLast(L, i)			// List 포인터 L, 원소 i
	new <- createNode(); 	// 새로운 노드 생성
    new.data =i;		// 데이터 필드 작성
    new.link = NULL;		//new가 마지막 노드임
    
    if(L=NULL) then  {		//빈 List일때, 최초 노드 추가
        L = new;
    	return;
    }
    temp = L;			//노드 링크 이용하여 List 순회
    while (temp.link !=NULL) do	//마지막 노드 찾을때까지 이동
    	temp = temp.link;
    temp.link = new;		//마지막 노드 추가
end addtoLast()

 

• List의 임의의 위치에 노드를 삽입하는 알고리즘
  - 노드 pre의 다음 위치에 노드 삽입

add(L, pre, i)			// List 포인터 L, 노드 pre, 원소 i
	new <- createNode(); 	// 새로운 노드 생성
    new.data =i;		// 데이터 필드 작성
    
    if(L=NULL) then  {		//빈 List일때
        L = new;		// List의 처음으로 지정
    	new.link = NULL;	//new가 마지막 노드임
    }
    else  {
    	new.link = pre.link;	//pre의 다음 노드의 new의 다음노드로
        pre.link = new;		//pre 다음 노드는 new
	}
end add()

 

단순 연결 리스트의 삭제 연산

•  'A', 'B', 'C', 'D' 원소를 갖고 있는 리스트의 'B'노드를 삭제

    1. 삭제할 노드의 앞 노드(선행노드) 탐색)  

    2. 삭제할 노드의 링크 필드를 선행노드의 링크 필드에 복사

• 노드를 삭제하는 알고리즘
  - 노드 pre의 다음 위치에 있는 노드 삭제

delete(L, pre)				// List L, 노드 pre
    if (L==NULL) then error;
    else {
    	target = pre.link;		// 삭제 노드 지정
        if (target == NULL) then return;
        pre.link = target.link;
    }
    freeNode(target);		//할당된 메모리 반납
end delete()

 

이중 연결 List 

- 양쪽 방향으로 순회할 수 있도록 노드를 연결한 List

- 두 개의 링크 필드와 한 개의 데이터 필드로 구성

Double Linked List

 

이중 연결 리스트의 삽입 연산

•  cur가 가리키는 노드 다음으로 D 값을 가진 노드를 삽입하는 과정

    1. 메모리를 할당하여 새로운 노드 new를 생성하고 데이터 필드에 'D' 저장

    2. cur의 next를 new의 next에 저장하여 cur의 다음 노드를 삽입할 노드의 다음 노드로 연결

    3. new의 값을 cur의 next에 저장하여 삽입할 노드를 cur의 다음 노드로 연결

    4. cur의 값을 new의 prev 필드에 저장하여 cur를 new의 이전 노드로 연결

    5. new의 값을 new가 가리키는 노드의 다음 노드의 prev 필드에 저장하여 삽입하려는 노드의 다음 노드와 삽입하려는 노드를 연결

 

이중 연결 리스트의 삭제 연산

• cur가 가리키는 노드를 삭제하는 과정

    1. 삭제할 노드의 다음 노드의 주소를 삭제할 노드의 이전 노드의 next필드에 저장하여 링크를 연결

    2. 삭제할 노드의 다음 노드의 prev 필드에 삭제할 노드의 이전 노드의 주소를 저장하여 링크를 연결

    3. cur가 가리키는 노드에 할당된 메모리를 반환

 

 

5) List 자료구조의 활용

Stack

• Stack의 원소 : List의 노드
  - Stack 내의 순서는 List의 링크를 통해 연결된다.
  - Push : List의 마지막 노드를 삽입한다.
  - Pop : List의 마지막 노드를 반환/삭제한다.
• 변수 Top
  - List의 마지막 노드를 가리키는 변수이다.
  - 초기 상태 : Top = Null
• List를 이용한 stack의 연산 
  - 원소 삽입시 탑 노드가 삽입된 원소의 주소를 가리키고, 삽입된 원소는 그 이전에 삽입된 원소의 주소를 가리킨다.
  - 원소 반환 시에는 탑 노드가 삽입된 원소가 가리키던 원소의 주소를 가리키고, 반환된 원소의 메모리를 해제한다.
• push/ pop 연산을 연결 리스트로 구현

우선순위 Queue

• 배열을 이용한 우선순위  큐
  - 원소를 삽입하는 과정에서 우선순위를 비교하여 적절한 위치에 삽입하는 구조이다.
  - 가장 앞에 최고 우선순위의 원소가 위치한다.
  - 배열을 사용하므로, 삽입이나 삭제 연산이 일어날 때 원소의 재배치가 발생하며 이에 소요되는 시간이나 메모리 낭비가 크다.
• List를 이용한 우선순위 큐
  - 원소를 삽입하는 과정에서 List 내 노도의 원소들과 비교하여 적절한 위치에 노드를 삽입하는 구조이다.
  - List의 가장 앞쪽에 최고 우선순위가 위치하게 된다.
  - 삽입/삭제 연산 이후 원소의 재배치가 필요 없다.
  - 메모리의 효율적인 사용이 가능하다.

 

오늘의 결론.

 

인덱스를 이용해서 데이터를 가져오는 것이 빈번하다면 ArrayList가 훨씬 유용한 자료구조!

데이터의 추가/삭제가 빈번하다면 LinkedList가 훨씬 효과적!!