Category (50) 썸네일형 리스트형 6-4. 연결리스트 (이중 연결 리스트) 이중 연결 리스트: 하나의 노드가 선행 노드와 후속 노드에 대한 두 개의 링크를 가지는 리스트 헤드 노드(head node): 데이터를 가지지 않고 오로지 삽입, 삭제 코드를 간단하게 할 목적으로 만들어진 노드 - 헤드 포인터와의 구별이 필요 - 공백 상태에서는 헤드 노드만 존재 자료 출처: 천인국 외 1명, C언어로 쉽게 풀어쓴 자료구조, 생능출판(2019) 6-3. 연결리스트 (원형 연결 리스트) 원형 연결 리스트 - 마지막 노드의 링크가 첫 번째 노드를 가리키는 리스트 - 한 노드에서 다른 모든 노드로의 접근이 가능 - 헤드 포인터가 마지막 노드를 가리키게끔 구성하여 리스트의 처음이나 마지막에 노드를 삽입하기 용이 1. 원형 연결 리스트의 처음에 삽입 2. 원형 연결 리스트의 끝에 삽입 자료 출처: 천인국 외 1명, C언어로 쉽게 풀어쓴 자료구조, 생능출판(2019) 6-2. 연결리스트 (단순 연결 리스트) 연결리스트 - 리스트의 항목들을 노드(node)라고 하는 곳에 분산하여 저장 - 노드는 데이터 필드와 링크 필드로 구성 데이터 필드: 리스트의 원소, 즉 데이터 값을 저장하는 곳 링크 필드: 다른 노드의 주소 값을 저장하는 장소(포인터) 장점 - 삽입, 삭제가 용이하다. 시간 복잡도는 O(1) - 연속된 메모리 공간이 필요 없고, 크기 제한이 없다. 단점 - 구현이 어렵고, 오류가 발생하기 쉽다. 연결 리스트의 종류: 단순 연결 리스트, 원형 연결 리스트, 이중 연결 리스트 단순 연결 리스트 - 하나의 링크 필드를 이용하여 연결, 마지막 노드의 링크 값은 NULL 단순 연결 리스트의 연산 - insert_first(): 리스트의 시작 부분에 항목 삽입 - insert(): 리스트의 중간 부분에 항목 삽입.. 6-1. 연결리스트 (배열을 이용한 구현) 배열로 구현된 리스트: 순차적인 메모리 공간이 할당되므로, 이것을 리스트의 순차적 표현이라고 한다 파일 시스템과 디스크 관리하기 물리적 디스크 - 디스크 용량 = 전체 실린더 수 x 트랙 수 x 섹터 수 x 섹터당 바이트 수(512) 디스크와 파티션 - 하드디스크의 파티션: 디스크를 논리적 파티션으로 구분하며 파티션 별로 파일목록 부분과 파일 데이터 부분으로 구성 파티션의 구성 - 부트블록: 부팅을 위한 프로그램 저장, 모든 파티션의 첫 블록 - 슈퍼블록: 파일 시스템에 관련된 주요 내용들 그 외 파일 목록 부분, 파일 데이터 부분 파일과 파일 시스템 파일: 연속된 하나의 저장 공간으로 바이트 단위로 기록 파일 시스템: 파일을 기록하고 관리하는 방식. 배치 및 생성/삭제/읽기/쓰기 등의 작업 처리를 포함. 파티션 별로 특정 파일 시스템 적용 1. 리눅스 파일 시스템의 종류 - ext(ext1): 1992년 4월 발표 - ext2:.. 프로세스 관리하기 1. 프로세스의 개념 프로세스: 현재 시스템에서 실행 중인 프로그램 - 프로세스는 부모-자식 관계를 가짐 - 부팅할 때 스케쥴러가 실행한 프로세스인 systemd(1번)와 kthreadd(2번) 프로세스를 제외한 모든 프로세스는 부모 프로세스를 가짐 - 자식 프로세스는 할 일이 끝나면 부모 프로세스에 결과를 돌려주고 종료 - 각 프로세스가 갖는 고유한 번호를 PID라고 함. - 현재 프로세스의 개수를 알 수 있는 방법 ps -e | wc 특수한 상태의 프로세스 데몬 프로세스: 특정 서비스를 제공하기 위해 존재, 부팅 과정에서 실행 시작 고아 프로세스: 아직 실행 중인데 부모 프로세스가 먼저 종료된 자식 프로세스, 1번 프로세스가 새로운 부모 프로세스가 되어 고아 프로세스의 작업 종료 지원. 좀비 프로세스.. 5. 큐 1. 큐의 특징 - 선입 선출: 먼저 들어온 데이터가 먼저 나감. - 뒤에서 새로운 데이터가 추가되고 앞에서 데이터가 하나씩 삭제되는 구조. - 삽입이 일어나는 곳을 후단, 삭제가 일어나는 곳을 전단이라고 함. - 삽입과 관련된 변수를 rear, 삭제와 관련된 변수를 front라고 함. 큐의 추상 자료형 - create(max_size): 최대 크기가 max_size인 공백큐를 생성. - init(q): 큐를 초기화. - is_empty(q): 큐가 공백상태인지 검사. - is_full(q): 큐가 포화상태인지 검사. - enqueue(q, e): 큐의 끝에 데이터를 추가. - dequeue(q): 큐의 앞에 있는 데이터를 삭제하고 반환. - peek(q): 큐의 맨 앞에 있는 데이터를 읽어서 반환. 2.. 4. 스택 1. 스택 - 후입 선출: 가장 최근에 들어온 데이터가 가장 먼저 나감. 스택의 추상 자료형 - push(s, item): 스택 맨 위에 데이터를 추가, 스택이 가득 차서 입력이 불가능하면 오류 발생. - pop(s): 스택 맨 위에 있는 원소를 삭제하고 반환, 스택에 데이터가 없어서 출력이 불가능하면 오류 발생. - is_empty(s): 스택이 공백상태인지 검사. - is_full(s): 스택이 포화상태인지 검사. - create(size): 최대 크기가 size인 공백 스택을 생성. - peek(s): 스택의 맨 위의 원소를 제거하지 않고 반환. 2. 스택의 구현 - 요소를 저장할 1차원 배열과 top 변수를 구조체로 정의 top 변수: 스택이 비어 있으면 -1의 값을 가짐. 0의 값을 가지면 안 .. 이전 1 2 3 4 5 6 7 다음
