자료구조 (Singly LinkedList)

Singly LinkedList

• 노드가 데이터와 참조값(주소값)을 가지고 직렬적으로 연결되어 있는 데이터 저장 구조
• 데이터 개수를 알수 없을 때 사용하기 좋음
• 배열보다 메모리를 효율적을 사용할 수 있다
• 탐색속도는 배열보다 상대적으로 느리다Node
• LinkedList에서 Node는 데이터와 다음 Node에 대한 참조값을 가지고 있다. (next변수 사용)
• 데이터 구조를 구성하는 개체이다.

연결(Linked)

• 다음 Node 참조값을 저장하여 다음노드에 접근하는 것을 연결이라함

LinkedList 구조

• Head : 가장 첫번째 Node의 참조값을 가지고 있다.
  (Node가 없다면 null값을 가진다.)
• Node : 데이터와 다음 Node 참조값을 가짐
• Pointer 개념 :Node의 참조값을 일시적으로 저장하는 변수(자바에는 포인터가 없지만 이해를 포인터 처럼 한다.)

삽입

• 리스트에 노드를 삽입할 시 두가지 방법이 있다.

1. Head가 있는 앞부분에 삽입
2. 리스트 중간에 삽입

• 맨 앞에 Node 삽입 순서
  1. Pointer가 Head에 위치했을 때, 새로운 Node를 생성한다.
  2. Head 다음 Node 참조값을 새로운 Node의 참조값에 저장한다.
  3. head의 새로운 Node 참조값을 저장한다.
• 중간 Node 삽입 순서 (Noda A와 Node B 사이에 넣을 때)
  1. Pointer가 Node A에 위치했을 때 , 새로운 Node를 생성한다.
  2. 새로운 Node는 Node A가 가지고 있는 Node B의 참조값을 저장한다.
  3. Node A는 새로운 Node의 참조값을 저장한다.
• 위의 순서를 지켜야 연결이 끊어지지 않는다.

삭제

• 삭제도 두가지 방법이 있지만 삽입에 비해 간단하다.
• 맨 앞에 있는 Node 삭제 : 삭제할 Node 다음 Node 참조값을 head에 저장한다. (나머지 작업은 참조가 되어있지 않으면 GC에 의해 소멸된다)
• 중간에 있는 Node 삭제 순서
  1. Pointer를 삭제 Node전에 위치
  2. 삭제할 Node의 next 변수로 다음 Node의 참조값을 알아낸다.
  3. 알아낸 참조값을 삭제 전 Node에 저장
  4. 삭제할 전/후 Node가 연결된다. (나머지 과정은 GC에 의해 진행)