리스트

순차리스트(배열)

• 특정 자료형이 메모리 공간상에 연속적으로 이루어져 있는 자료구조

특징

• 메모리상에 연속적으로 저장되기 때문에 데이터 접근 속도가 빠르다.
• 인덱스를 통해 접근하기 때문에 어떤 열에 접근하더라도 속도가 같다.
• 배열의 최대크기를 변경할 수 없다.
• 삽입/삭제 시 자료의 이동이 발생한다.
  -> 데이터를 삽입하거나 삭제하고 나면, 연속적인 물리적 위치를 유지하기 위해 원소를 옮기는 추가 작업이 필요하기 때문에

배열의 메소드

깃허브 정리

연결리스트

• 여러개의 흩어진 노드들이 연결된 형태의 자료구조
• 어떤 object를 갖는 노드를 담고 있고 연결이라는 단어 그대로 next 변수(포인터 역할)로 다음에 어떤 노드를 가리키는지 나타낸다.

특징

• 하나의 노드는 자료와 링크로 구성된다.
• 특정 노드를 삽입하거나 삭제할 때 노드의 링크 필드(다음 노드 주소)만 수정하면 되므로 순차 리스트에 비해 연산 속도가 빠르다.
• head(첫 번째 노드) -> next -> ... -> tail(마지막 노드) -> (null)
• 자료들 외에 링크를 저장하는 변수가 필요함으로 배열보다 메모리 효율이 떨어진다.
• 이전 노드를 통해서만 다음 노드를 참조할 수 있다는 특성 때문에 리스트의 처음부터 다음 노드들을 탐색해야해서 속도가 느리다.
• 링크가 중간에 끊어지면 다음 노드를 찾기 어렵다.

단순 연결 리스트 (singly linked list) : 한 쪽 방향의 ptr
이중 연결 리스트 (doubly linked list) : 양쪽 방향의 ptr
환형 연결 리스트 (circular linked list) : 순환

연결리스트 메소드

깃허브 정리

스택

• LIFO(Last In First Out) : 후입선출 >> 요소가 추가되면 아래로 쌓여 출력 시 가장 위(마지막에 추가한 요소)부터 출력된다.

특징

• 리스트의 마지막 인덱스에서 삽입과 삭제 연산을 수행한다.
• 함수 호출 순서 제어, 인터럽트 처리, 수식계산 등에서 사용한다.

스택 함수 구현

깃허브 정리

큐

• FIFO(First-In First-Out) : 선입후출 >> 줄을 서서 기다리는 것 처럼 먼저 추가되면 가장 먼저 출력된다.

특징

• 스케줄러, 대기 순서에 따라 처리되는 연산 등에서 사용한다.

큐 함수 구현

깃허브 정리