[TIL - Codesquad] 자료구조, 배열, 리스트, ArrayList, LinkedList, Doubly Linked List

TIL [210111]

 

Linked List(연결 리스트, 링크드 리스트)

ko.wikipedia.org/wiki/%EC%97%B0%EA%B2%B0_%EB%A6%AC%EC%8A%A4%ED%8A%B8

- 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 자료구조.
- 노드의 포인터가 다음 노드와의 연결을 담당함.
- 장점 : 데이터의 추가와 삭제가 O(1)의 시간에 가능함
- 단점 : 특정 데이터 검색에 O(n)의 시간이 걸림

 

자료구조란 무엇인가?

opentutorials.org/module/1335/8634

자료구조 (Data Structure, 데이터 스트럭쳐)

: 데이터를 효율적으로 저장하고, 꺼내기 쉽게 만드는 것.
(꺼내쓰기 쉽게 데이터를 잘 정리정돈하는 것)
자료구조를 잘 활용해 시스템을 효율적으로 설계할 수 있다.

 

배열 Array

opentutorials.org/module/1335/8677

배열은 대표적인 자료구조 중 하나이다.

- 각 데이터에 인덱스가 있기 때문에 데이터의 조회가 빠르다.
- 중복된 데이터를 허용한다

단점
- 어떤 인덱스에 값을 추가하면, 기존 값은 삭제된다 - 덮어씌워지기 때문
- 어떤 인덱스에 값이 삭제되면, 그 값 대신 null이 들어간다 - 메모리 낭비 초래 & null체크 필요.

-> 인덱스가 가장 중요한 경우 배열을 사용한다.

 

리스트 List

opentutorials.org/module/1335/8636

데이터가 null같은 빈틈없이, 연속적으로 위치하는 자료구조.
- "순서가 있는" 데이터구조 - 그래서 리스트를 시퀀스(sequence, 순서)라고도 한다.
- 빈 자리가 허용되지 않는다 - 어떤 값이 삭제되면 뒤의 값들이 그 자리를 채운다
- 중복된 데이터를 허용한다

단점
- 데이터 자리가 수시로 바뀌므로, 인덱스를 식별자로 사용할 수 없다.

-> 인덱스가 중요하지 않은 경우 리스트를 사용한다.

ArrayList와 LinkedList의 비교

ArrayList는 인덱스를 통해 데이터를 조회할 때 더 유리하다.
LinkedList는 데이터의 추가/삭제가 빈번할 때 더 유리하다.

 

ArrayList

opentutorials.org/module/1335/8709

배열을 이용해서 리스트를 구현한 리스트.

장점
- 인덱스를 통한 데이터조회가 빠르다.
(내부적으로 배열을 이용하기 떄문에 인덱스를 사용 가능) 

단점
- 데이터 추가 / 삭제가 느리다.
(데이터 추가 : 뒤의 데이터들을 한 칸씩 뒤로 밀어야 하기 때문)
(데이터 삭제 : 뒤의 데이터들을 한 칸씩 앞으로 당겨야 하기 때문)

 

LinkedList

opentutorials.org/module/1335/8821

: 요소 간의 연결(link)을 이용해서 리스트를 구현한 것.

컴퓨터의 동작원리

컴퓨터의 3가지 주요부품

1. 메모리 : = RAM
 - 속도가 매우 빠른 대신, 용량이 작다
 - 전원이 꺼지면 데이터가 사라진다.
 - 실행속도를 결정한다.
 

2. 스토리지 : HDD, SSD
 - 속도가 느린 대신, 용량이 크다
 - 전원이 꺼져도 데이터가 남아 있다.
 - 데이터는 기본적으로 스토리지에 저장된다.
 - 프로그램을 실행하면, 프로그램과 데이터는 스토리지에서 메모리로 옮겨진다(load).

3. CPU 
 - 메모리에 로드된 데이터를 이용해 작업을 한다.

 

메모리가 실행속도를 결정하기 때문에,
성능을 높이려면 메모리를 효율적으로 사용해야 한다.
이것이 자료구조를 배우는 이유이다.(메모리를 효율적으로 사용하기 위해)

 

메모리의 구조와 ArrayList, LinkedList

- 메모리 구조를 자세히 알고 싶다면 '컴퓨터 구조 computer architecture)'를 공부해야.

- ArrayList에 포함된 데이터들은 한 덩어리로 함께 저장된다.
 : ArrayList 크기가 커져 더 많은 공간이 필요해지면, 자리가 부족하기 때문에 자리가 있는 곳으로 ArrayList자체를 옮겨야 한다.
 : ArrayList의 데이터 하나는 element (요소) 라고 한다.

- LinkedList에 포함된 데이터들은 서로 다른 위치에 저장된다.
 : 각 데이터는 바로 뒷 데이터의 위치만 알고 있다.
 : 특정 데이터를 찾으려면 처음부터 시작해 연결된 데이터를 모두 탐색해야 한다.
 : LinkedList의 데이터 하나는 node (노드, 마디라는 뜻) 또는 vertex(버텍스, 꼭지점이라는 뜻) 라고 한다.

 

LinkedList의 구조 - 노드 Node

: LinkedList는 노드의 모임이다.
- LinkedList는 어떤 값을 탐색하기 위해 head가 가리키는 노드부터 순차적으로 찾아야 한다.

노드 Node

노드의 구성요소 2가지
1. 노드의 값 (data field)
- value와 같은 변수를 할당한다.
2. 다음 노드 (link field)
- next변수를 사용한다 - 다음 노드의 포인터나 참조값을 저장.
- 참조값을 통해 노드와 노드를 연결한다.

Head

LinkedList의 맨 앞부분.
- LinkedList가 건물이라면 head는 출입문이다.
- LinkedList를 사용하려면 head가 가리키는 첫 번째 노드를 찾아야 한다.

 

Java로 LinkedList 구현하기

opentutorials.org/module/1335/8857

LinkedList - Java 구현 - Data Structure (자료구조)

 

 

Doubly Linked List(이중 연결 리스트)

opentutorials.org/module/1335/8940

Doubly Linked List와 기존 LinkedList의 차이는 노드가 양방향으로 연결되어 있다는 것이다.
1. 이전 노드 (Previous Link Field)
2. 노드의 값 (data field)
3. 다음 노드 (Next Link Field)

장점
: 양방향으로 연결되어 있어 노드를 양쪽으로 탐색할 수 있다.
- 특정 인덱스의 노드를 가져올 때, 반복문으로 탐색할 때 유용하다.
- 앞뒤로 탐색이 가능하다.
- 노드 위치가 첫 요소와 가까우면 맨 처음부터, 끝 요소와 가까우면 맨 끝부터 탐색할 수 있다 (탐색시간 감소)

단점
- 이전 노드 previous link field를 지정하기 위해 변수를 하나 더 사용해야 한다 = 메모리를 더 많이 사용
- 구현이 더 복잡해진다
-> 장점이 더 크기 때문에 실제 사용되는 linkedlist는 대부분 doubly linked list이다.

 

Java로 Doubly Linked List 구현하기

opentutorials.org/module/1335/8941

Doubly linked list - Java 구현 - Data Structure (자료구조)

 

 

** 내일 할 일 **

빅오표기법 영상, 자료 보고 공부하기 www.youtube.com/watch?v=6Iq5iMCVsXA&feature=youtu.be

미션 본격적으로 구현하고 얼른 제출하기