[자료구조] 연결리스트

기본적인 단일 연결리스트를 기준으로

데이터의 구조와 추가,삭제에 대한 설명입니다.

---

1. 연결 리스트란?

먼저, 리스트는 데이터를 순서대로 나열한 자료구조이다.

리스트의 형태

위의 그림 처럼 순서가 있으며 각각의 데이터가 나열되어 있는 형태이다.

연결 리스트는 나열된 불연속적인 데이터를 서로 연결한 형태이다.

연결 리스트의 구조

각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하고 있다.

이때 리스트의 데이터는 노드 또는 요소라고 한다.
각각의 노드는 데이터와 다음 노드를 가리키는 포인터를 가지고 있다. (위의 그림에서 회색 선)

하나의 노드를 기준으로 바로 앞에 있는 노드를 앞쪽 노드(predecessor node),

바로 뒤에 있는 노드를 다음 노드(successor node)라고 한다.

 

< 배열의 단점 >

• 크기를 변경할 수 없다.
• 비순차적인 데이터의 추가, 삭제에 시간이 많이 걸린다.
  (배열 중간 데이터를 추가하려면 빈자리를 만들기 위해 데이터 복사, 이동 과정이 필요하다.)

-> 연결 리스트는 이러한 배열의 단점을 보완한다.
    배열처럼 데이터를 복사, 이동하는 과정 없이 노드 간의 참조 변경만으로 데이터 추가, 삭제가 가능하다.

 

2. 연결 리스트의 데이터 추가, 삭제

1) 머리에 노드 삽입

머리에 노드 삽입

삽입 될 새로운 노드(F)를 생성, 생성한 노드를 참조하도록 head를 업데이트

기존 머리 노드를 삽입된 노드의 다음 노드로 연결

 

2) 꼬리에 노드를 삽입

꼬리에 노드 삽입

리스트가 비어있는지 아닌지를 확인하고 작업을 수행

• 리스트가 비어있을 경우

  머리에 노드를 삽입 하는 것과 동일

• 리스트가 비어 있지 않은 경우

  리스트 꼬리에 새로운 노드를 삽입

3) 머리 노드 삭제

머리 노드 삭제

리스트에 노드가 한개만 있어도 오류없이 삭제 가능

 

4) 꼬리 노드 삭제

꼬리 노드 삭제

리스트에 노드가 몇개 있는지에 따라 해당 작업을 수행

• 리스트에 노드가 1개인 경우

  머리 노드를 삭제하는 작업과 같음

• 리스트에 노드가 2개 이상인 경우

  꼬리 노드와 꼬리 노드로부터 두번째 노드를 찾는다.
  꼬리 노드로부터 두번째 노드의 뒤쪽 포인터에 null을 대입
  어디에도 참조되지 않을 꼬리노드는 자동으로 해지 될 것

5) 선택 노드 삭제

선택 노드 삭제

선택한 노드가 머리 노드인지 아닌지에 따라 작업을 수행

• p가 머리 노드인 경우

  머리 노드를 삭제

• p가 머리 노드가 아닌 경우

  p의 앞쪽 노드를 찾는다. (ptr이 참조하게 됨)
  p의 뒤쪽 포인터 p.next를 ptr의 ptr.next에 대입
  ptr의 뒤쪽 포인터가 p의 다음 노드를 참조하도록 업데이트 한다.
  어디에도 참조되지 않는 노드 p의 메모리는 자동으로 해지된다.

(p는 삭제되기 위해 선택된 노드이다.)