[Java][1]LinkedList란?

개인 공부 후 자료를 남기기 위한 목적이기에 내용 상에 오류가 있을 수 있습니다.

---

목표

• LinkedList란 무엇인지 이해합니다.
• visualgo.net을 통해서 LinkedList 자료구조가 데이터를 추가, 삭제 , 검색하는 과정을 이해합니다.

 

목차

1. LinkedList란?

2. 데이터 조작 과정

(1) 데이터 추가

(2) 데이터 삭제

(3) 데이터 검색

 

 

 

 

1. LinkedList란?

각 노드가 '데이터'와 '포인터'를 가지고 한 줄로 연결되어 잇는 방식으로 저장하는 자료구조

*데이터 : 실제 값이 저장되는 장소.

*포인터 : 다음 노드의 주소값이 저장되는 장소

 

 쉽게 말해 LinkedList는 엘리먼트와 엘리먼트 간의 연결(Link)을 통해서 리스트를 구현한 자료구조입니다. 배열을 통해서 리스트를 구현한 ArrayList와는 대비됩니다.

 ArrayList에선 각각의 데이터를 담은 요소들을 엘리먼트(element)라고 표현하였지만 LinkedList는 각각의 요소들이 연결이라는 특성을 가지기 때문에 "node(마디,교점)"혹은 "vertex(꼭지점, 정점)"라고 표현합니다. 이러한 노드를 표현하기 위해서 C언어는 '구조체'를 사용하고 객체지향 프로그래밍 언어에선 '객체'를 사용합니다.

 

LinkedList구조  및 특징

그림 1 (ArrayList 자료구조)

 

그림 2 (LinkedList 자료구조)

Data field : 실제 값이 저장되는 변수입니다.

Link field : 다음 노드의 포인터나 참조값을 저장하는 변수입니다.

node(or vertex) :  LinkedList에서 데이터가 저장되는 요소입니다. Data field와 Linke field로 구성되었습니다.

HEAD : 첫번째 노드를 가리키는 변수.

 

 ArrayList구조(그림 1)의 경우 하나의 주소 값에 배열을 생성하여 데이터들을 저장하였습니다. 그와 다르게 LinkedList의 경우 데이터가 저장되는 하나하나의 요소들이 주소 값을 차지합니다. 이러한 개개의 요소들은 LinkedList에서 노드라고 표현되는데 이렇게 흩어진 노드들은 각 노드들이 다음 노드를 지목함으로써 데이터들 간에 관계를 가지게 됩니다.

 

 LinkedList에서 저장한 값을 찾기 위해서든, 값을 추가하거나 삭제하든 반드시 첫번째 노드 값을 알아야만 데이터를 다룰 수 있습니다. 따라서 첫 번째 노드를 가리키는 HEAD는 linkedList에서 매우 중요합니다.

 

 

 

2.  데이터 조작과정

 이번 포스팅에선 LinkedList가 데이터를 검색, 삭제, 추가하는 과정을 이해해보고자 합니다. 왜냐하면 이 과정을 이해한다면 LinkedList가 ArrayList에 비해 데이터를 추가하고 삭제하는 것이 왜 빠른지와 LinkedList가 ArrayList에 비해 데이터를 검색하는 과정은 왜 늦는지를 알 수 있기 때문입니다. 

 LinkedList의 데이터 추가와 삭제는 visualgo.net 홈페이지를 통해서 이해해보고자 합니다.

 

 

(1) 데이터 추가

 LinkeList에서 새로운 노드를 추가하는 전체 적인 과정은 다음과 같습니다. ( 편의를 위해서 새로 추가될 노드를 'new노드', 새로추가 될 노드의 바로 앞 노드를 'before노드', 새로 추가될 노드의 바로 뒤 노드를 'after노드'라고 지칭하겠습니다.)

 

1. 가장 먼저 'new노드'와 'before노드'를 찾습니다.

2. 'new노드'를 생성합니다.

3. 'before노드'의 Link field(다음 노드를 가리키는 참조값을 저장하는 변수)를 'new노드'를 가리키도록 변경합니다.

4. 'new 노드'의 Linke filed를 'after노드'를 가리키도록 변경합니다.

 

데이터 추가 속도 : ArrayList < LinkedList 

 위의 과정을 보게 되면 LinkedList에서 새로운 노드를 추가하는 방식은 ArrayList에서 새로운 엘리먼트를 추가하는 방식보다 훨씬 간결하다는 것을 알 수 있습니다. ArrayList는 내부적으로 크기를 변경할 수 없는 배열을 사용하기 때문에 데이터를 추가할 시엔 크기가 더 큰 배열을 생성해서 값을 옮겨야 하는 복잡한 과정을 거치기 때문입니다.

 

visualgo.net을 통해서 보는 데이터 추가

 아래와 같이 구성된 LinkedList에서 3번째 노드에 90을 삽입해보겠습니다. 그림 3의 왼쪽 아래 화살표 내비게이션을 누르고 [삽입] => [sepecify both in[1..N-1]and v =]을 선택 후 첫 번째 공란에 2(순서, 첫번째 노드를 배열과 똑같이 0번째라고 보기 때문), 90(넣을 값)을 삽입합니다. 그리고 [실행]을 누르면 데이터가 추가(삽입)되는 과정을 볼 수 있습니다. 

그림 3

 

가. pre라는 변수에 첫번째 노드(1번째 노드, 값 : 22)를 저장시킵니다.

그림 4

 

나. for문을 통해서 pre변수에 우리가 삽입하고자 하는 노드의 앞 노드(2번째 노드, 값 2)를 저장시킵니다.

그림 5

 

그림 6

 

그림 7

 

 

다. atf변수에 우리가 추가하고자 하는 순서에 기존에 있던 노드(순서 2, 값 : 77)를 저장합니다. 

그림 8

 

라. aft변수에 우리가 지정한 순서에 기존에 있던 노드이자 삽입한 노드의 다음 순서가 될 노드(현재는 3번째지만 삽입 후 4번째, 값 : 77)를 저장시킵니다.

그림 9

 

마. 넣고자 하는 값을 가진 새로운 노드를 생성하여 vtx변수에 저장합니다.

그림 10

 

바. 새로운 노드(vtx)의 Link field에 aft변수를 저장합니다.

그림 11

 

사. 새로 추가될 노드 바로 앞 노드(pre)의 Link field에 vtx 변수를 저장합니다.

그림 12

 

 

(2) 데이터 삭제

 LinkeList에서 노드를 삭제하는 전체 적인 과정은 다음과 같습니다. ( 편의를 위해서 삭제될 노드를 'delete노드', 삭제될 노드의 바로 앞 노드를 'before노드', 삭제될 노드의 뒤에 있는 노드 'after노드'라고 지칭하겠습니다.)

 

1. 'before노드', 'delete노드', 'after노드'를 찾습니다.

2. 'before노드'의 Link field(다음 노드를 가리키는 참조값을 저장하는 변수)를 'after노드'를 가리키도록 변경합니다.

3. 'delete노드'를 삭제합니다.

 

데이터 삭제 속도 : ArrayList < LinkedList 

 데이터의 삭제 또한 데이터의 추가와 같은 이유로 ArrayList보다 LinkedList의 방식이 훨씬 간결하고 빠릅니다.

 

visualgo.net을 통해서 보는 데이터 삭제

 아래와 같이 구성된 LinkedList에서 3번째 노드에 77을 삭제해보겠습니다. 그림 13의 왼쪽 아래 화살표 내비게이션을 누르고 [삭제] => [sepecify i in[1..N-2]]을 선택 후 첫 번째 공란에 2(순서, 첫번째 노드를 배열과 똑같이 0번째라고 보기 때문) 삽입합니다.. 그리고 [실행]을 누르면 데이터(노드)가 삭제되는 과정을 볼 수 있습니다. 

그림 13

가. pre라는 변수에 첫 번째 노드(1번째 노드, 값 : 22)를 저장시킵니다.

 

나. for문을 통해 pre에 삭제될 노드 바로 앞 노드(순서 2, 값 : 2)를 저장시킵니다.

그림 15

 

그림 16

 

그림 17

 

다. del변수에 삭제될 노드를 저장시키고 aft변수에 삭제될 변수 뒤의 노드를 저장시킵니다.

그림 18

 

라. 삭제될 노드 바로 앞노드(pre)의 Link field에 aft변수(삭제될 노드 뒤의 노드)를 저장합니다.

그림 19

 

마. 삭제하고자 했던 노드(del 변수)를 삭제합니다.

그림 20

 

(3) 데이터 검색

 LinkeList에서 특정 순서 노드의 데이터 값을 찾기 위해선 다음과 같습니다. 

 

1. head를 통해 제일 첫 번째 노드에 진입합니다.

2. 자신이 찾고자 하는 순서의 노드가 아니면 Link field를 통해서 다음 노드에 진입합니다. (자신이 찾고자 하는 순서의 노드에 도달할 때까지 해당 과정을 반복합니다.)

3. 찾고자 하는 순서의 노드에 도달한 경우 해당 노드의 데이터 값을 반환합니다.

 

 

데이터 검색 속도 : ArrayList > LinkedList 

 데이터를 검색하는 속도는 ArrayList가 압도적으로 빠릅니다. ArrayList의 경우 각각의 값들이 순서 값을 가지고 있기 때문에 찾고자 하는 순서만 안다면 해당 데이터 값에 빠른 접근이 가능합니다. 하지만 LinkedList의 경우 특정 순서의 값을 알고자 하는 경우 첫 노드에 진입하여 자신이 찾고자 하는 순서의 노드까지 반복적으로 노드에 진입해야만 값을 얻을 수 있기 때문에 긴 시간이 소모됩니다. 

 

 

3. 정리

LinkedList란?

• LinkedList는 엘리먼트와 엘리먼트의 연결(Link)을 통해서 리스트를 구현한 자료구조입니다.
• LinkedList에선 엘리먼트를 node 혹은 vertex라고 부릅니다.
• 하나의 노드는 값을 저장하는 Data field와 다음 노드를 가리키는 값인 Linke field로 구성되어 있습니다.
• head는 제일 첫 번째 노드를 의미합니다.
• LinkedList에서 데이터를 검색, 삭제, 추가 작업을 하기 위해선 반드시 첫 번째 노드에 진입해야 합니다.

LinkedList vs ArrayList 속도 비교

• 데이터 추가, 삭제 :  ArrayList < LinkedList
• 데이터 검색 : ArrayList > LinkedList

Reference

• https://opentutorials.org/module/1335/8821
• visualgo.net

 

 

Date

• 2020.05.11 작성