알고리즘 - 리스트

✔ 리스트

• 리스트(List) : 순서를 가진 데이터의 집합을 가리키는 추상 자료형(abstract data type)
  • 데이터 중복 허용, 순서 => 순서는 index를 통해 관리. 삽입하는 순서.
  • 구현 방법
    • 순차 리스트 : 배열을 기반으로 구현된 리스트
      • 물리적 공간 연속적(offset 적용)
    • 연결 리스트 : 메모리의 동적 할당을 기반으로 구현된 리스트
      • 자바 객체 "new"를 통한 동적 객체 생성.

1. 순차 리스트

• 구현 방법
  • 1차원 배열에 항목들을 순서대로 저장.
  • 데이터의 종류와 구조에 따라 구조화된 자료구조를 만들어 배열에 저장 가능.
• 데이터 접근 : 배열의 인덱스ㅡ를 이용해 원하는 위치의 데이터에 접근.
• 삽입 연산 : 삽입 위치 다음의 항목들을 뒤로 이동해야 한다.
• 삭제 연산 : 삭제 위치 다음의 항목들을 앞으로 이동해야 한다.
• 문제점
  • 단순 배열 이용시 자료의 삽입/삭제 연산 과정에서 연속적인 메모리 배열을 위해 원소 이동 작업 필수.
  • 삽입/삭제 연산이 빈번하게 일어나는 경우 작업 소요 시간이 크게 증가(O(N))
  • 배열의 크기가 정해져 있는 경우
    • 사용될 메모리보다 크게 할당하여 메모리 낭비 초래 가능.
    • 할당된 메모리 보다 많은 자료를 사용하여 새롭게 배열을 만들어야 하는 경우 발생 가능.

2. 연결 리스트(Linked List)

• 특성
  • 자료의 논리적인 순서와 메모리 상의 물리적인 순서 일치 X.
    • 각 원소를 연결하여 하나의 전체 자료구조 구성.
  • 링크를 통해 원소에 접근. 물리적인 순서를 맞추기 위한 작업 필요없음.
  • 자료구조의 크기 동적으로 조정 => 효율적인 메모리 사용.
• 기본 구조 : 노드 + 헤드
  • 노드 : 연결 리스트에서 하나의 원소를 표현하는 Building Block
    • 구성 요소
      1. 데이터 필드(data) : 원소의 값 저장. 저장할 원소의 종류나 크기에 따라 구조 정의하여 사용.
      2. 링크 필드(link) : 다음 노드를 참조값을 저장
  • 헤드 : 연결 리스트의 첫 노드에 대한 참조값

• 연결 리스트 종류
  • 단순 연결 리스트
    
  • 이중 연결 리스트
    
  • 원형 연결 리스트
    • 단순 원형 연결 리스트
      
    • 이중 원형 연결 리스트
      

3. 단순 연결 리스트

• 연결 구조

  • 노드가 하나의 링크 필드에 의해 다음 노드와 연결되는 구조.
  • 헤드가 가장 앞의 노드를 가리키고, 링크 필드가 연속적으로 다음 노드 가리킴.
  • 링크 필드가 Null인 노드가 마지막 노드.

• 삽입 연산 : 첫 번째 노드로 삽입

/* 
Head -> newNode -> beforeHead -> ... -> Null
새로운 노드를 헤드로 만들고, 이전의 노드들은 새 노드의 링크에 연결.
*/
void addtoFirst(L, i){
	Node newNode = new Node();
    newNode.data = i;
    newNode.link = L;
    L = d;
}

• 삽입 연산 : 마지막 노드로 삽입

/*
Head -> ... -> newNode -> Null
새로운 노드를 이전 마지막 노드의 링크에 연결.
void addtoLast(L, i){
	Node newNode = new Node();
    newNode.data = i;
    newNode.link = null;
    
    if (L == null){
    	L = newNode;
        return;
    }
    
    temp = L;
    while (temp.link != null){
    	temp = temp.link;
    }
    temp.link = newNode;
}
*/

• 삽입 연산 : 가운데 노드로 삽입

/*
Head -> ... -> newNode -> ... -> null
기준 노드를 찾아 새로운 노드를 연결시키고, 기준 노드의 링크를 새로운 노드의 링크로 넘겨 준다.
*/
void add(L, pre, i){
	Node newNode = new Node();
    newNode.data = i;
    newNode.link = null;
    if (L == null){
    	L = newNode;
    }else{
    	newNode.link = pre.link;
        pre.link = newNode;
    }
}

• 삭제 연산

/*
Head -> A -> B -> C -> null
1. A 삭제 : Head -> B -> C -> null / A -> null
  - Head는 B로 변경.
  - A 링크 null.
2. B 삭제 : Head -> A -> C -> null / B -> null
  - A 링크 C(B의 링크).
  - B 링크 null.
3. C 삭제 : Head -> A -> B -> null / C -> null
  - B 링크 null.
*/
void delete (L, target){
	if (L == null || target == null) return;
    pre = getPreNode(target);	// 선행 노드 탐색
    // 첫 노드인 경우
    if (pre == null){
    	L = target.link;
    }else{
    	pre.link = target.link;
    }
    target.link = null;
}

4. 이중 연결 리스트