[자료구조] 5강 - 연결 리스트

✅ 1. 리스트의 개념

(1) 배열의 정의

• 배열은 하드웨어 메모리의 물리적인 순서와 동일함 ( 실제 메모리의 물리적 주소 공간에 연속적으로 저장됨. )
• 원소의 메모리 공간(메인 메모리, DDR)의 물리적인 위치를 '순서'적으로 결정하는 특징
• 배열의 순서는 메모리 공간에서 저장되는 '원소값의 물리적 순서'

(2) 리스트의 의미

• 여러 개의 데이터를 어떤 정의에 의해서 결정된 논리적인 순서대로 묶어서 관리할 수 있는 자료구조를 말한다.
• 리스트의 '순서'는 데이터가 저장되는 물리적인 위치와 상관없이 사람들의 머릿속에 인식되는 '논리적인 순서', 혹은 리스트에서 나타나는 원소들 간의 '의미적인 순서'를 의미한다.
• 배열은 인덱스로 표현되는 '추상적 순서'가 배열 원소의 메모리 공간에서의 물리적인 위치와 일치함.
• 하지만, 리스트의 '순서' 개념은 어떤 정의에 의해서 결정된 '논리적인 순서' 이며, 원소들의 물리적인 저장 순서나 위치와는 무관하게 원소들 간의 논리적인 순서만 유지함
• 쉽게말해, 하드웨어 메모리에 어떻게 저장되느냐는 중요하지 않고, 결론은 사람이 보는 논리적인 순서만 유지하면 됨.
• 이렇게 논리적인 순서만 유지해준다면 그것을 리스트라고 부름

(3) 리스트의 구현 방법

• 포인터를 이용한 리스트의 구현 방법: 원소값을 저장하는 공간과 다음 원소를 가리키는 위치 정보를 저장하는 공간을 함께 구현하는 방법이다.
• 배열을 이용한 리스트의 구현 방법: 배열을 활용하여 메모리의 배열 순서대로 저장하는 방식
• 즉, 논리적인 순서만 유지해주면 되는것이 리스트이기 때문에 이렇게 다양한 구현이 가능함.

---

✅ 2. 배열을 이용한 리스트의 구현

(1) 배열을 이용한 리스트의 구현

• 배열을 사용하므로, 배열처럼 메모리에 연속적인 순차적 주소값을 갖게 된다.

(2) 배열을 이용한 리스트의 문제점

• 메모리 낭비: 초기 배열 선언에서 충분히 크게 하면 어느 정도 배열의 추가 확장을 피할 수 있겠지만, 확장 된 공간을 활용을 안한다면 그 만큼의 메모리 공간이 낭비가 될 수 있는 문제가 있음.
• 연산 시간의 증가: 원소를 삽입하거나 삭제하기 위해서는 해당 원소의 위치 뒤에 있는 모든 원소를 뒤로 물리거나 앞으로 당겨야만하는 문제가 있음. ( 중간 삽입 시 뒤로 밀고, 중간 삭제시 뒤에 원소를 앞으로 당겨야함 )
• 리스트 원소값의 이동은 원소 수가 많을수록 그만큼 프로그램의 수행시간을 증가시킨다. ( 원소들이 이동을 해야해서 )
• 리스트의 원소 삽입은 프로그램의 실행 중에 메모리 할당을 필요로 하는 경우도 발생시킴
• 배열을 이용한 리스트의 구현은 실제 IT 서비스 환경에서는 자주 사용되지 않고 있음.
• 자료의 삽입과 삭제가 빈번히 발생하는 상황에서 리스트를 배열로 구현하는 것은 빈번한 자료 이동으로 인한 비효율적인 컴퓨팅 성능을 유발함.

---

✅ 3. 포인터를 이용한 리스트의 구현

포인터를 위한 메모리 할당이 필요함

작은 수의 데이터에서 포인터를 쓰면 낭비가 될 수 있음.

(1) 노드의 구조

• 노드(node): 리스트의 원소값(데이터) + 다음 원소를 가리키는 정보(포인터) 가 합쳐져서 하나의 노드가 된다.
• 노드는 데이터 요소(원소값)와 리스트의 다음 노드를 지시하는 포인터(주소, 링크)로 구성됨 -> 위엔 값 아래엔 주소

(2) 노드의 구조 및 연결

• 해당 노드 하나에는 연결 된 노드 다음 노드의 메모리 주소값과 데이터를 가지고 있다.

(3) 연결 리스트의 논리적 순서와 실제 메모리 표현

• 연결 리스트의 노드 구성은 실제 메모리 주소값과 데이터를 가지고 있으며, 해당 주소값은 본인의 주소값이 아닌 연결 된 다른 노드의 주소값이다.
• C/C++은 연결 리스트 노드가 실제 메모리 주소를 저장함.
• Java는 가상 주소(참조) 를 저장하고 JVM이 이를 실제 메모리에 매핑을 한다.
• 하지만 JVM도 결국 메모리에서 노드들을 연결을 하며, 실제 물리 주소는 JVM이 알아서 관리를 해주게 됨. 추상화 느낌

---

✅ 4. 포인터 변수

(1) 리스트의 생성

• C 언어에서 연결 리스트 구현한 자료구조이다.

(2) 포인터의 할당과 반환 예

• 메모리를 할당 받고 포인터를 지정받고 값을 할당받는 과정이다.

(3) 포인터의 할당과 반환의 실행 결과

• p_a 와 p_b 변수명으로 메모리 공간을 각각 자료형 바이트 크기에 맞게 할당을 받은 모습이다.
• 각각 주소값을 메모리의 주소값이 있고, 연결 된 다른 노드의 주소값을 가지고 있다.

---

✅ 5. 연결 리스트의 삽입과 삭제

(1) 연결 리스트에서 노드의 삭제

• link 의 숫자는 다음 노드의 메모리 주소값이다.

 

• 삭제 될 노드의 link 를 호출하는 전 노드의 link 값을 삭제 될 노드의 다음 노드로 연결을 해주면 삭제가 이루어진다.

[ 리스트의 원소 삭제 연산 단계 ]

• 삭제할 노드의 선행 노드의 링크 필드를 삭제할 노드의 후행 노드를 가리키게 한다.
• 삭제할 노드를 메모리에 반환한다. ( 운영체제에게 넘김으로써 해당 부분은 삭제 되며, 다른 영역으로 씌임 )

(2) 연결 리스트에서 노드의 삽입

• 초기 연결 리스트에서 메모리 주소값 6000을 갖는 노드가 만들어졌다고 가정

 

• 삽입할 위치를 선택을 하면 선행 그 사이의 선행 노드의 link 필드 값을 삽입 될 노드의 메모리 주소로 넣어주고 삽입 된 link 필드 값을 후행 노드의 link 값으로 넣어주게 된다. 이렇게 되면, 삽입이 된 것처럼 보이는데 결국엔 연결만 한 것임. 즉, 메모리의 연속적이 아닌 비연속적으로 저장이 됨을 알 수 있음. 애초에 메모리 주소값 자체가 다 달라서 비연속적임.

[ 리스트의 원소 삽입 연산 단계 ]

• 메모리 공간을 할당받고 삽입할 내용을 저장하여 삽입할 x 노드를 생성한다.
• x 노드의 링크부분이 후행 노드가 될 j 노드를 가리키게 한다.
• 삽입될 x 노드의 선행 노드가 될 i 노드의 링크 필드가 x 노드를 가리키게 한다.

---

✅ 6. 연결 리스트의 여러 가지 연산

(1) 연결 리스트의 생성

• 연결 리스트의 생성 연산을 의미하고 있으며, 연결 리스트를 만들게 되면 처음엔 head 에 주소값을 가진 형태로 있게 되며, 이후 노드가 추가되면 헤드에서 data 와 link 를 가지는 노드를 연결하게 되는 구조이다.
• 처음 만들어지면 head 노드만 존재하므로 head 가 가지는 주소값은 NULL 이 될 수 있다는 의미이다.

(2) 연결 리스트의 삽입

• 노드를 삽입하는 경우에는 새로운 노드가 만들어지는 경우이다.
• 즉, New Node 가 만들어지며, 내부 데이로는 x , link 로는 NULL 인 새로운 노드가 만들어지게 된다.

• 연결 리스트의 노드를 삽입 할 때 현재 리스트가 공백인 경우에는 NewNode를 만들고 제일 앞인 head 의 link 에 후행 노드인 앞에서 만든 NewNode 의 주소값을 넣어주게 바로 리턴을 하게 되는 연산이다.
• 현재 리스트가 공백인 경우로 head 노드가 NULL 인 경우 후행 노드가 없으므로 해당 리스트는 빈 리스트로 볼 수 있다.
• 즉, 이 경우에는 새로운 노드를 만들어 head 노드의 참조 주소값을 새로 만들어지는 노드의 주소값으로 넣으면 된다.

[ 연결 리스트 뒤에 여러 노드가 있는 상태에서 새로운 노드 삽입 연산 ]

• 새로 만들어지는 NewNode 가 있다면, LastNode 를 찾아서 해당 LastNode 의 link 부분에 NewNode 의 주소를 넣게됨.
• 기본적인 원리는 while 반복문을 통해 조건을 수행하게 된다. 해당 조건은 LastNode 는 항상 link 가 무조건 NULL 이어야 하기 때문에 NULL 노드를 타고 가면서 NULL 인 노드가 있는지 파악을 하게 된 후, 있다면 그곳을 LastNode 로 보고 그 곳에 만들어진 후행 노드의 주소값을 넣어주게 되는 방식이다.

[ 연결 리스트의 특정 노드 뒤에 새 노드의 삽입 연산 ]

• 특정 노드 뒤에 새 노드를 삽입 할 때 이 특정 노드는 prevNode 로 불린다.

• 위와 같은 연산을 하면 해당 그림과 같은 결과를 가질 수 있게 된다.
• prevNode 뒤에 NewNode 를 넣을 땐 prevNode 와 연결 된 기존 노드의 주소값을 NewNode 의 link 에 넣어주게 됨.
• 이후, prevNode 의 link 값을 NewNode 의 주소값으로 변경을 해줌으로써, 중간에 껴넣을 수 있게 됨.

• 이후, 결과는 이런 모습이 될 수 있음.

(3) 연결 리스트의 삭제 연산

[ 연결 리스트 마지막 노드 삭제 연산 ]

• 조건문 첫 번째를 보면 head 의 link 값이 NULL 즉, 공백 리스트인 경우: 삭제 할 것이 없으므로 연산이 중단이 된다.
• 리스트에 노드가 한 개인 경우: head 의 link 값을 NULL로 변경하면 알아서 연결이 끊기며, 운영체제가 날려줌.
• 즉, 하나만 있는 경우에는 head 의 값만 변경하면 됨.

• 리스트에 노드가 여러 개 있는 경우: prevNode 와 delNode 포인터를 이용 할 수 있으며, link 값이 NULL 인 경우를 찾을 때 까지 반복문을 돌리면서 prevNode 와 delNode 를 한칸씩 뒤로 가게 한다. 찾으면 그때 prevNode의 link 값을 NULL 로 바꾸면서 연결이 끊기며 삭제가 되는 연산임.

(4) 연결 리스트 특정 노드 검색

• 검색은 삭제 연산인 deleteNode 를 활용하여 진행을 하게 된다.
• 기존 마지막 삭제 연산과 마찬가지로 prevNode 와 delNode 를 한 칸씩 뒤로 밀면서 중간의 조건문으로 data 값이 내가 원하는 data 값인지 여부를 체크를 하게 된다. 이후, 아닐 경우에 다시 미는 방식을 이용하게 된다.
• 이러한 방식을 이용해서 특정 위치의 데이터를 검색 할 수 있으며, 특정 위치의 데이터를 삭제 또한 할 수 있게 된다.

• 위와 같이 prevNode 와 delNode 접근을 통해 특정 노드를 파악 할 수 있으며, 이것은 검색과 마찬가지로 삭제도 가능하다.

• 이러한 연산을 통해서 특정 위치의 노드를 삭제하고 삭제된 노드의 선행 및 후행 노드를 연결해줄 수 있다.

• prevNode 의 link 를 삭제 할 노드의 후행 노드의 주소값을 참조하게 되고, delNode 의 후행 노드와 연결을 끊음으로써 삭제가 될 수 있음.