선형자료구조 _ 연결리스트(단일, 이중, 환형)

연결 리스트 (단일, 이중, 환형): 논리적으로 연결

배열과 연결 리스트의 차이

 

배열은 정해진 크기 안에서 순차적 자료구조

연결 리스트는 크기가 정해져있지 않은 순차적 자료구조

연결리스트의 종류

1) 단일 연결 리스트 (이동시 ++ 연산만 가능)

2) 이중 연결 리스트 (이동시, --, ++ 연산 가능)

3) 환형 연결 리스트 (단일 or 이중) : 마지막 노드가 첫번째 노드를 가르킨다.

1. 단일 연결 리스트

* 노드(Node): [데이터 저장소 + 링크(다음 노드의 주소를 저장하는 공간)] 로 구조를 갖는다.

==> 링크를 통해 논리적 선형 구조 완성한다!

단일 연결 리스트 구현 Step1) 

1. 노드 정의

2. 연결 리스트 구조체 정의

 

단일 연결 리스트 구현 Step2)

초기화(생성자 구현)

 

단일 연결 리스트 구현 Step3)

front_Insert 

 

ex. 빈 강의실에 학생 입실 (생활 예시)

1) 책상[Node]를 들고 입실 ==> 노드 생성

2) 아무데나 책상을 놓는다 ==> 노드를 초기화(데이터저장, null)

3) 논리적 연결 ==> 노드를 앞에 연결(front_insert) 

   3-1) 비어있을 때

 

   3-2) 노드가 존재할 때

 

단일 연결 리스트 구현 Step4)

selectAll(선형 순회)

1. 순회할 레퍼런스 변수 선언 <== 첫번째 노드

Node cur = head;

 

2. cur을 다음 노드로 이동

cur = cur.next;

 

3. 언제까지?

cur ==  null 일때 이동을 멈춰야한다.

 

단일 연결 리스트 구현 Step5)

back_insert 

 

1. 노드 생성 및 초기화

2. 연결

   2-1. 노드가 비어있을 때

      front_insert() 와 구현과 동일

   2-2. 노드가 존재할때

     

단일 연결 리스트 구현 Step6)

front_delete

 

1. 삭제할 노드를 찾는다.

2. 노드가 없는 경우

3. 노드가 있는 경우

   3.1 삭제 후 노드가 없는 경우

   3.2 삭제후 노드가 있는 경우

단일 연결 리스트 구현 Step7)

 

back_delete

 

1. 삭제할 노드를 찾는다. (꼬리 찾기)

2. 노드가 없는 경우

3. 노드가 있는 경우

   3.1 삭제할 이전의 노드를 찾는다.

 

 

단일 연결 리스트 구현 Step7)

public boolean random_insert(Node cur, Object data) 

=> cur 다음에 data값을 갖는 노드를 추가

1. 노드 생성 및 초기화

2. 그림에 있는 개의 연결 흐름 작성

3. size 1 증가

4. true 반환 

※ 주의!

cur의 위치가 마지막 노드인 경우에도 생각해 주어야한다.

 

단일 연결 리스트 구현 Step8)

public boolean random_delete(Node prev)

==> 삭제 이전의 prev 노드를 매개변수로 받아 del.next 노드와 연결

 

1. 삭제 연결 연산

   1.1 만약 3을 삭제해야하는 상황

      => prev를 알아둔다음 del.next 노드와 연결

   1.2 만약 4를 삭제해야하는 상황

     => del.next = null 

2. size 1 감소

3. true 반환

 

 

2. 이중 연결 리스트

* 노드(Node): [링크(이전 노드의 주소를 저장하는 공간) +데이터 저장소 + 링크(다음 노드의 주소를 저장하는 공간)] 

로 구조를 갖는다.

 

이중 연결 리스트 구현 Step1)

1. 노드 정의

2. 연결 리스트 구조체 정의

이중 연결 리스트 구현 Step2)

MyDList 생성자 (default 생성자, 인자 없는 생성자)

 

이중 연결 리스트 구현 Step3)

boolean push_front(Object data) 

==> 노드 생성 초기화 -> 연결

 

1. 비어있는 상황

2. 노드가 존재하는 상황

이중 연결 리스트 구현 Step4)