[생활코딩!] JAVA LinkedList, Doubly Linked List 간단한 소개 및 정리

JAVA Arraylist(배열)에 이어 Linkedlist(리스트)에 대해 이야기 해보도록 하겠습니다.

먼저 이해를 돕기 위해, 자세한 소개 및 설명에 앞서 컴퓨터의 동작 원리에 대해 살펴 보도록 하겠습니다.

1. 컴퓨터의 3대부품과 데이터 처리속도에 대한 설명

컴퓨터에는 CPU, Storage, Memory라는 3개의 중요한 부품이 있음

일반적으로 파일은 Storage에 저장함

: Storage에는 HDD와 SSD가 있음.

: Storage는 가격이 저렴함, 용량이 크고 전원이 꺼도 내용이 저장됨

: 그러나 Storagr는 매우 느려서 CPU와 일을 함께 하기에 속도면에서 너무 부족함.

Memory는 자료구조에 중요한 부품임

: Memory는 가격이 비싸고 용량이 적고, 전원을 끄면 사라짐,

: Momoey가 Storage 보다 빠르게 데이터를 가져오올 수 있음

: 그러므로 프로그램의 실행속도를 결정하는 것은 대표적으로 메모리임

CPU가 연산을 할 때(프로그램을 실행을 시킬때), 필요한 데이터는 Memory를 통해서 가져옴

그러므로 자료구조를 배우는 이유는 Memory를 효율적으로 사용하기 위함

RAM의 특징(Random Access Memory)

데이터 주소(Address)를 알고 있으면 빠르게 데이터를 가져올 수 있음

2. Linked List

1) Linkedlist란?

- linkedlist 이해하는 key는 linked 연결

- Linked List는 엘리먼트와 엘리먼트 간의 연결(link)를 이용해서 리스트를 구현한 것을 말함

2) Linked list의 구조

- node(마디, 교점), vertex(정점, 꼭지점)

- node는 두개의 변수가 있음

   Data Field : 저장하는 값 (예 10)

   Link filed : 다음 노드가 무엇인지 저장되어있음

- HEAD : 첫번째 노드가 무엇인지 의미하는 정보가 저장됨

3) ArrayList와 Linked List의 차이

Arraylist와 Linked list 메모리 사용방식에서 차이가 있음

Arraylist는 같은 앨리먼트들이 메모리상에 연속적으로 붙어 있음

Linked list는 각각의 엘리먼트들이 흩어져있음, 그러나 연결되어 있음

Array List와 Linked List의 트래이드 오프는 아래와 같다

(트래이드 오프 란 어떤 특성이 좋아지면, 다른 특성이 나빠지는 상황을 말한다)

3. Doubly Linked List

1) 간단한 특징 : Doubly Linked List는 예측가능한 것처럼 Linked List의 탐색 기능이 강화된 리스트임

2) 구조 : 위의 이미징 보듯 이전 노드와 다음 노드로 구성되어, 노드의 양방향 탐색이 가능함

3) 장점

- 인덱스의 데이터를 가져올 때 앞부터 탐색을 시작하거나 뒤부터 탐색을 시작할 수 있음

- 노드 탐색

: 이중 연결 리스트는 앞뒤 탐색이 가능.

: 상황에 따라 탐색 방향이 바뀌어야 하는 경우면 Linked List보다 Doubly Linked List가 유리함

4) 단점

이전 노드 지정을 위해 변수를 하나 더 사용해야 하기 때문에 더 많은 메모리가 사용됨

하지만, 장점이 크기 때문에 현실에서 사용하는 연결 리스트 대부분은 이중 연결 리스트임