순차리스트 및 연결리스트

1.리스트란?

• 리스트는 우리들이 자료를 정리하는 방법 중의 하나이다.
• 리스트는 스택과 큐와 달리 제한 없다.
• 리스트는 스택과 큐와 달리 임의의 위치에서도 요소의 삽입과 삭제가 가능한 선형 자료구조이다.

2.배열과 리스트의 차이

• 메모리 할당: 배열은 연속적인 메모리 공간에 할당되고, 리스트는 비연속적인 메모리 공간에 할당된다.
• 크기: 배열은 크기가 고정되어 있으며, 리스트는 가변적이다.
• 접근 방법: 배열은 인덱스를 통한 빠른 접근이 가능하지만, 리스트는 순차적으로 접근해야 한다.
• 삽입과 삭제: 배열은 삽입과 삭제가 번거롭고 시간이 오래 걸리지만, 리스트는 삽입과 삭제가 빠르다.

3.순차 리스트(ArrayList)

리스트를 가장 쉽게 구현하는 방법은 배열을 이용한 방식이다.
<삽입>

void insert(int pos, int e)
{
 int i;
 if(is_full==0&&pos>=0&&pos<=length)
 {
  for(i=length;i>pos;i--)
  {
   data[i]=data[i-1];
  }
  data[pos]=e;
  length++;
 }
 else error("포화상태 오류 또는 삽입 위치 오류");
}

여기서 pos라는건 그냥 position을 나타내는 약어.

<삭제>

void delete(int pos)
{
  int i;
  if(is_empty()==0&&0<=pos&&pos<length)
  {
   for(i=pos+1;i<length;i++)
   {
    data[i-1]=data[i];
   }
   length--;
  }
  else error("공백상태 오류 또는 삭제 위치 오류");
}

4-1.연결 리스트(ArrayList)란?

연결 리스트(Linked List)는 데이터 구조의 한 종류로, 노드(Node)들이 순차적으로 연결된 형태로 구성되어있다. 각 노드는 데이터와 다음 노드를 가리키는 포인터로 이루어져 있다. 연결 리스트는 배열과 유사하지만, 배열과 달리 크기가 고정되어 있지 않고 동적으로 확장될 수 있다. 이를 통해 삽입과 삭제가 보다 유연하게 이루어진다.

4-2.연결 리스트(ArrayList) 특징?

• 동적 크기: 배열과 달리 연결 리스트는 노드를 추가하거나 제거하면서 크기를 동적으로 조절할 수 있습니다.
• 비연속적 저장: 배열은 메모리 상에 연속적으로 저장되지만, 연결 리스트는 각 노드가 비연속적으로 저장되어 있다. 각 노드가 다음 노드의 위치를 가리키므로, 연결된 구조를 유지할 수 있다.
• 노드 삽입 및 삭제: 배열에서는 중간에 값을 삽입하거나 삭제할 때 많은 이동이 필요하지만, 연결 리스트에서는 포인터만 조정하면 되기 때문에 상대적으로 간단하게 수행할 수 있다.

4-3.연결 리스트(ArrayList) 종류?

• 단일 연결 리스트(Singly Linked List): 각 노드가 다음 노드에 대한 포인터만 가지고 있는 구조
  
• 이중 연결 리스트(Doubly Linked List): 각 노드가 다음 및 이전 노드에 대한 포인터를 가지고 있어, 양방향으로 순회가 가능.
  
• 원형 연결 리스트(Circular Linked List): 마지막 노드가 첫 번째 노드를 가리키는 구조로, 연결 리스트의 순회가 원형으로 이루어지게 한다.
  

4-4.연결 리스트(ArrayList) 핵심 요소?

• 노드(Node): 링크드 리스트의 기본 단위로서, 데이터를 저장하는 데이터 필드 와 다음 노드를 가리키는 링크 필드 로 구성된다.
• 포인터:각 노드 안에서, 다음이나 이전의 노드와의 연결 정보를 가지고 있는 공간
• 헤드(Head): 링크드 리스트에서 가장 처음 위치하는 노드를 가리킨다. 리스트 전체를 참조하는데 사용된다.
• 테일(Tail): 링크드 리스트에서 가장 마지막 위치하는 노드를 가리킨다. 이 노드의 링크 필드는 Null을 가리킨다.

4-5.연결 리스트(ArrayList) 연결 리스트의 장단점

• 장점
  1.동적 메모리 할당을 통해 메모리 관리가 유연합니다.
  2.삽입과 삭제가 배열에 비해 빠르게 이루어질 수 있습니다.
• 단점
  1.각 노드가 포인터를 포함하므로, 배열에 비해 메모리 사용량이 증가할 수 있다.
  2.인덱스를 통해 직접 접근할 수 없어, 특정 위치의 노드를 찾기 위해 처음부터 순회해야 한다.

4-6.연결 리스트(ArrayList) 삽입 삭제

<삽입>

<삭제>