리스트(List) - 1

✔️ List

List

• 추상 자료형으로 구성, 순서중요x, 중복o
• Set: 순서중요x, 중복x
• Linear

Sorted vs Unsorted

• 정렬 vs 정렬x

Array vs Linked Representation

• Array: Element(Data)
• Linked list: Node(Data, Next Link), Head Pointer

Stack, Queue, Deque, List(Unsorted)

(Unsortd) List ADT

• Insert Position (0 ~ length): 특정 포지션에
• Delete from Position (0 ~ length-1): 특정 포지션에
• Peek Position (0 ~ length-1): 특정 포지션의 요소 반환
• Is List Empty?

Sorted List ADT

• Insert: 요소를 정렬된 리스트에 삽입
• Delete: 키와 함께 제거
• Search: 찾고 키 반환
• Is List Empty?

✔️ Array Representation if (unsorted) List

(Unsorted) Array List

• 요소들이 배열에 저장되어 있다
• Vector 또는 Sequence라고도 알려져 있다
• length = # of element is list
• Position(Index) of element = 0 ~ length-1

Main Operation (List ADT)

• Insert Position (0 ~ length): 특정 포지션에
• Delete from Position (0 ~ length-1): 특정 포지션에
• Peek Position (0 ~ length-1): 특정 포지션의 요소 반환
• Is List Empty?

Other Operation

• Search Element with Key
• Print List
• Is List Full?
• Insert Front, Insert Rear
• Delete Front, Dlete Rear, …

Array Implement of List

• 요소들이 배열되어 있는 중간에 데이터를 집어넣을때는 오른쪽으로 Shift한 후 집어넣는다.
  • O(n)
• 마찬가지로 중간에 데이터를 삭제할 때는 왼쪽으로 Shift 한 후 빈공간을 채운다.
  • O(n)

Stack, Queue vs Array List

• Stack을 Array로 구현하면 데이터를 넣고 뺄 때 O(1)이다.
• Queue를 Array로 구현하면 데이터를 넣을 때 O(n)이다.
• 따라서 Stack은 Array로 구현해도 상관이 없지만 Queue는 Array로 구현하는 것이 비효율적이다.

Usage

• ArrayList.h

...
typedef int Data;

class ArrayList{
	...
	void insertPos(int pos, Data d);
	Data DeletePos(int pos);
	Data PeekPos(int pos);
	void PeintList();
	bool IsE mpty();
};

Application

• Polynomial Addition: 오퍼레이터 연산자 사용
• Matrix: 오퍼레이터 연산자 사용
• Stack and Queue using Array List
• Deque using Array List
• Array List for Stusent Info: 스택과 큐에서는 템플릿을 사용
• Array List for Stusent Pointer: 한번에 많은 내용이 Shift 할 때 많이 사용, 포인터만 바꿔치기
• Bank Simulation with Leaving: 중간에 들어왔다 나올 때 큐보다 유용, 기다리다가 시간이 모자르면 줄을 이탈하는 경우 추가

✔️ Array Reprentation of Sorted List

Sorted Array List

• 장점
  • 빠른 탐색: using bynary search
  • 빠른 선택: ex) 최댓값, 최솟값, 중앙값

Main Operations (List ADT)

• Insert
  • Shift Right O(n)
• Delete
  • Shift Left O(n)
• Search
• Is List Empty?

Other Operations

• Delete Front, Print List, Is List Full?

Usage

...
typedef int Data;

class Sorted List : public ArrayList{
	...
	void insert(Data d);
	Data Delete(int key);
	Data Srarch(int key);
	float Median();
	void SetAlgorithms(...) // set search Algorithms
	...
};

Application

• Score to Letter Grade
• Flight Database
• sorted Array List for Student Info: 정렬되었기 때문에 탐색 용이, 하지만 데이터를 집어넣고나 빼는것이 빈번하다면 비효율적

✔️ Linked List

Linked List

• 비엔나 소시지처럼 포인터가 다음거를 연결
• 하나하나를 노드라고 부름
• 노드가 쭉 연결
• Head가 첫번째 node를 가리킴
• 맨 끝에는 Null
• 노드는 데이터이다.
• Dynamic하게 데이터를 할당

Structure of Linked List

• Node(Data, Next Link)
• Head poonter
• Dynamic memory allocation and deallocation

Kinds of Linkde Lists

• (singly) Linked List
  • head pointer
• (Circular) Linked List
  • head pointer
  • tail pointer
• Doubly Linked List
  • head and tail pointers
  • forward and backward traversals

Main Operations (List ADT) - Aray List와 동일

• Insert Position(0 ~ length)
  • O(1)

  head = new Node(20, head); // Insert to head
  p -> next = new Node(20, p -> next); // Insert to other position
  

• Delete Position (0 ~ length-1)
  • O(1)

  #define DELETE(a){ 
  	Node* temp = a; 
  	a = a -> next;
  	delete temp;
  }
  
  DELETE(head); // Delete from head
  DLETTE(p -> next); // Delete from other position
  

• Peek Position(0 ~ length-1)
• Is List Empty?

Other Operations

• Search Element with Key
  • O(n)

  for(Node* p = head; p != NULL; p = p -> next){
  	if(Key(p->data) == key) return p-> data;
  }
  

• Print List
  • Traverse Linked List
  • O(n)

  for(Node* p = head; p != NULL; p = p -> next){
  	cout << p -> data << " ";
  }
  

• Insert Front, Insert Rear
• Delete Front, Delete Rear, …

Usage

...
typedef int Data;

class LinkedList{
	...
	void insertPos(int pos, Data d);
	Data DeletePos(int pos);
	Data Peekpos(int pos);
	void PrintList();
	bool IsEmpty() {return head == NULL;}
	Data Delete(int key);
	Data Search(int key);
	void PrintData();
	...
};