[자료구조/선형자료구조]링크드리스트(연결리스트),스택

연결 리스트를 써야하는 상황 -> 몇개의 원소를 갖는지 미리 정하지 못하는 상황

장점 : 쉽고 빠른 추가/삽입/삭제

단점 :  원소의 참조(탐색)가 비효율적, 포인터 때문에 4byte추가 공간 필요

스택

선입 후출(먼저 들어가면 나중에 나오는) 구조

1. 배열 기반 스택

typedef int ElementType;

typedef struct tagNode

{

ElementType Data;

}Node;

typedef struct tagArrayStack //배열 기반 스택

{

int Capacity;

int Top;

Node* Nodes;

}ArrayStack;

스택을 배열로 구현 할 경우 구현이 상대적으로 간편하지만, 대신에 크기를 미리 정해야함.

연결리스트로 스택을 구현 할 경우 구현은 상대적으로 손이 더 가지만, 크기를 미리 정하지 않아도됨. 둘의 장단점이 반대임

2. 연결리스트 기반 스택

맨아래가 시작지점이고 맨위에가 끝지점임. 선입후출

1	typedef struct LinkedListStack

2

{

3	Node* List;

4	Node* Top;

5

6	} LinkedListStack;