서론

연결리스트(Linked List)의 이론정리와 golang으로 직접 구현까지 할 예정이다만..
연결리스트를 진행하기 앞서 자료구조에서 리스트에 관한 이론만 간략하게 정리하고 들어가려고 한다.

---

1. 자료 구조

1) 자료 구조의 개념

• 자료 구조는 컴퓨터상의 자료를 효율적으로 저장하기 위해 만들어진 논리적인 구조
• 자료 구조의 현명한 선택을 통해 효율적인 알고리즘을 사용할 수 있게 하여 성능을 향상

2) 자료 구조의 분류

구조	설명	종류
선형 구조	데이터를 연속적으로 연결한 자료 구조	리스트, 스택, 큐, 데크
비선형 구조	데이터를 비연속적으로 연결한 자료 구조	트리, 그래프

• 대략적인 자료구조의 분류

3) 선형 구조

(1) 리스트(List)

• 다량의 데이터를 다루는데 가장 단순한 방법
• 순서와 위치를 지님

① 선형 리스트(Linear List)

• 배열과 같이 연속되는 기억 장소에 저장되는 리스트
• 선형 리스트의 대표적인 구조로는 배열(Array)등이 있음
• 가장 간편한 자료 구조이며, 접근 구조가 빠름
• 자료의 삽입, 삭제 시 기존 자료의 이동이 필요

② 연결 리스트(Linked List)

• 노드의 포인터 부분으로 서로 연결시킨 리스트
• 연결하는 방식에 따라 단순 연결 리스트, 원형 연결 리스트, 이중 연결 리스트, 이중원형 연결 리스트로 구분.
• 노드의 삽입, 삭제가 선형 리스트와 달리 편리
• 연결을 위한 포인터가 추가되어 저장 공간이 추가로 필요
• 포인터를 통해 찾는 시간이 추가되어 선형 리스트에 비해 다소 느림

(2) 스택(Stack)

• 스택은 한 방향으로만 자료를 넣고 꺼낼 수 있는 LIFO(Last-In First-Out)형식의 자료 구조이다.
• 한 방향으로만 Push와 Pop을 이용하여 자료를 넣고 꺼낸다.
  • Push : 데이터를 차례대로 스택에 넣는 연산
  • Pop : 스택에서 가장 위에 있는 데이터를 하나씩 꺼내는 연산
• Top은 스택에서 가장 위에 있는 데이터로, 스택 포인터라고도 불린다.
  

(3) 큐(Queue)

• 큐는 한쪽 끝에서는 삽입 작업이 이루어지고, 반대쪽 끝에서는 삭제 작업이 이루어지는 FIFO(First-In First-Out) 형식의 자료 구조이다.
• 한쪽에서는 Enqueue 연산을 이용하여 데이터를 넣고, 한쪽에서는 Dequeue 연산을 이용하여 데이터를 꺼낸다.
  • Enqueue : 데이터를 차례대로 넣는 연산
  • Dequeue : 처음 저장된 데이터부터 하나씩 꺼내는 연산
• 데이터가 꺼내는 쪽에서 가장 가까운 데이터를 Tail(Rear)라고 한다.
  

(4) 데크(Deque; Double Ended Queue)

• 데크는 큐의 양쪽 끝에서 삽입과 삭제를 할 수 있는 자료 구조이다.
• 두 개의 포인터를 사용하여, 양쪽의 삭제/삽입이 가능하다.
• 데크 연산에는 Push와 Pop이 있다.
  • Push : 데이터를 차례대로 데크에 넣는 연산
  • Pop : 데크에서 Front와 Rear에 있는 데이터를 하나씩 꺼내는 연산
• 데크를 이용한 스택과 큐의 구현이 가능하다.