Linked list 란?
Linked list정의
연결 리스트는 여러 개의 노드로 이루어져 있다. 각각의 노드는 데이터와 다음 노드가 뭔지 알려주는 주소를 가지고 있다. 또한 연결 리스트는 새로운 데이터를 추가하거나, 데이터의 위치를 찾거나, 제거하는 기능이 있어야 한다. Linked list는 일련의 원소를 배열처럼 차례대로 저장하지만, 원소들이 메모리상에 연속적으로 위치하지 않는다는 점이 다르다.
linked list를 배우기전 리스트에 대해 먼저 배워보자. 리스트는 자료구조중 하나로 데이터를 나란히 저장하며,중복된 데이터의 저장을 막지 않는다. 리스트는 자료구조 구현방법에 따라서 선형 리스트(Linear List)와 연결 리스트(Linked List)로 구분할수 있다
- 선형 리스트 (Linear List): 배열을 기반으로 구현된 리스트(배열 리스트)
- 연결 리스트(Linked List): 노드의 연결로 구현된 리스트
위 사진을 보면 Linked list의 흐름을 대충 이해할수 있을 것이다. Linked list 에서 원소는 원소 자신과 다음 원소를 가르키는 링크가 포함된 노드(Node)로 구성된다. 그림에서 보이듯, '데이터를 저장할 장소'와 다른변수를 가르키기 위한 장소가 구분되어 있는것을 알아볼수 있다.
제거
만일 연결 리스트의 data3를 제거하게 되면 어떤 일이 발생하는가? 사진을 보면 알수 있듯이 data1번 Node가 5번 Node로 연결되는 것을 알아볼수 있다. 여기서 배열과 큰 차이점이 나타난다. 배열에서 중간 인덱스의 값을 제거해준다면 어떻게 되는가? 그 배열은 중간이 빈 배열이 될것이다. Linked list는 배열의 단점을 효율적으로 보완할수 있다.
추가
3번째 그림을 보자 Node와 Node사이에 값을 하나 새로운 Node를 추가해주자. 그럼 어떤 변화가 일어나는가? 1번Node 가 2번 Node로 연결되고 2번이 5번 Node로 연결되는 것을 확일할수 있다. 여기서도 배열과 차이점이 나타난다. 배열에서 중간에 값을 추가하게 되면 한칸씩 밀어주지만 Linked list는 값을 추가한뒤 다음원소를 가르키는 연결만 바꿔주면 된다.
선형 리스트(Linear List)와 연결 리스트(Linked List)의 차이점
| Linear List | Linked List | |
| 읽기 | O(1) | O(n) |
| 삽입,삭제 | O(n) | O(1) |
Linked List 와 Linear List의 삽입과 삭제가 Linked List가 더 효율적이고 좋은지는 위 그림만 봐도 알수있다. 그러나 왜? 읽기는 배열(Linear List)이 더 효율적인가? Linked List 는 특정 요소를 검색하기 위해서는 Head부터 하나하나 검사할수밖에 없다. 왜냐하면 Node가 바로 다음 요소로 연결해주기 때문이다. 배열같은 경우는 해당 인덱스를 알면 바로 접근할수 있다는 차이점이 있다.
Linked List에 이러한 단점을 보완하기 위해 Doubly linked list가 있다. 이중 연결 리스트에 대해에서는 다음번에 알아보자...
Linked List의 특징
- 노드로 구성로 구성되어 있다.
- 노드에는 값과 다음 값에 대한 주소를 가지고 있다.
장점
- 크기에 제한을 가지고 있지 않다
- 중간 삽입 삭제가 array에 비하여 쉽다
- 삽입.삭제에 대한 비용이 적다 O(1)
단점
- 탐색에 있어 단방향이다
- 탐생에 대한 비용이 크다
- 때문에 삽입 삭제에 있어서 이전 노드의 주소(객체)의 정보를 가지고 있어야 한다.
property
- headNode: 헤드부분을 나타낸다.
- listarray: 배열을 선언해준다.
Mehod
- append(데이터): 리스트의 맨 끝에 데이터를 추가한다.
- removeAt(위치): 해당 위치에 있는 데이터를 삭제한다.
- indexOf(데이터): 해당 데이터의 인덱스를 반환한다. 존재하지 않을 경우 결과 값은 -1이다.
- remove(데이터): 데이터를 삭제한다.
- insert(위치, 데이터): 해당 위치에 데이터를 삽입한다.
- isEmpty(): 데이터가 하나도 없다면 true를, 그 외엔 false를 반환한다.
- size(): 데이터 개수를 반환한다. 배열의 length 프로퍼티와 비슷하다.
수도코드
pseudo code