Data Structure - Stack & Linked List

1. Stack(스택) - 쌓다 

- 큐와 다르게 데이터의 출입이 한쪽에서만 발생한다.

- 그러므로 가장 나중에 삽입된 데이터가 가장 먼저 나가는 구조를 갖고 있다.(LIFO - Last In, First Out)

 

[주요 기능]

• push(): 스택에 데이터 삽입
• pop(): 스택에서 데이터 꺼내기

 

[Stack 활용의 예]

- Stack은 프로세스 실행 구조의 기본이다. 그러므로 프로세스에서는 스택의 자료구조를 사용한다. 

 

[Stack 장점]

• 구조가 단순해서 구현이 쉽다.
• 데이터를 저장/읽기(검색) 속도가 빠르다.  → 프로세스 실행 구조로 사용하는 이유

[Stack 단점]

• 데이터의 최대 개수를 미리 정해야 한다. 
• 그렇기에 남는 공간이 생길 수 있다.(낭비 발생 - 이런 이유로 파이썬은 재귀함수를 1000번까지만 호출한다.)

 

[파이썬으로 Stack 만들기] 

- push() 대신 append()를 사용하고 pop()함수는 파이썬에 존재한다. 

---

2. Linked List(링크드 리스트, 연결 리스트) 

- Linked List는 Array(배열)의 단점이 보완된 형태의 자료구조로 크기가 가변적인 배열이다.

- 크기의 가변성을 위해 노드와 포인터를 사용하여 데이터를 저장하고 연결한다.

• Node(노드): 데이터의 저장단위로 데이터 값과 포인터(주소값)를 쌍으로 구성한다.    
• Pointer(포인터): 각 노드(데이터)의 다음과 이전 노드의 위치 정보(주소값)

[연결 리스트의 장점]

• 저장 공간을 미리 할당할 필요가 없다(저장공간이 가변적). 

[연결 리스트의 단점]

• 데이터간의 연결을 위해 포인터의 저장공간이 따로 필요하다(저장공간 효율이 안좋음).
• 포인터를 이용해 연결노드를 찾는 시간이 필요하다(접근 속도가 느림).
• 중간에 데이터가 삭제되면 삭제된 데이터의 다음과 이전 데이터의 연결을 재구성 해야한다. 

 

[파이썬으로 linked list만들기]

- 연결 리스트에서는 파이썬의 객체지향 프로그래밍에 대한 이해를 필요로 한다.

 

 

[연결리스트 중간의 데이터 삭제 후 연결 재구성하기]

 

 

[파이썬 OOP를 이용하여 연결리스트 구현하기]