연결리스트(linked list)
연결리스트 혹은 링크드리스트로 불리는 자료구조다. 개인적으로 C언어와 C++언어에서 이걸 구축하는데 굉장이 열받는 상황이 이어졌던 것으로 기억한다. 왜냐하면 JavaScript같은 고오오급 언어와 다르게, pointer라는 주소를 가르키는 똥같은 변수자료형이 있었기 때문이다. 덕분에 구현하는데만 피똥싸고, 뭔지도 모르고 끝나는 이상한 일이었다. 지금도 * 별모양만 보면 경기를 일으킨다. 이참에 이걸 공부해서 제대로 개념정리해놔야겠다고 스스로 다짐했다.(큐도 그렇고, 스택도 그렇고, 자바스크립트는 변수로 포인터를 사용하는 것 같아서 마음이 편안하다.)
그래서 연결리스트가 뭐람?
연결리스트는 위의 이미지처럼 데이터를 비엔나소시지처럼 연결시켜놓은 구조로 되어있는 자료구조다. 리스트의 맨 앞 첫 노드를 가리키는 변수가 HEAD === 대가리, 맨 뒷 데이터가 들어있는 곳이 TAIL === 꼬리가 된다.전체 노드는 추상적으로 Linked List라는 덩어리 안에서 구조를 이룬다. 각 노드에는 DATA를 담는 데이터부분과 NEXT노드를 가리키는 pointer 부분으로 나누어져 있다. NEXT pointer를 이용해서, 다음 자료를 순차적으로 조회하거나 탐색할 수 있다.
일렬로 배치되어있는 자료구조를 보고있으면 문득 배열이 떠오를 수 있다. 배열도 일종의 선형 자료형이기 때문이다. 그림으로 보게되면 배열과 연결리스트의 큰 차이점을 바로 알 수 있는데,
배열
- 순차적으로 데이터를 접근하는 것이 가능하다.(동일)
- index를 이용해서 바로 접근할 수 있다.
(시간복잡도 O(1)) - 배열에 데이터를 삽입한다면, 모든 데이터의
index값(address)가 변경되어야 한다.
(0번 index에 있던 자료가 1번 index로 이동, 1번 index에 있던 자료가 2번 index로 이동,,,)
(시간복잡도 O(n))
연결리스트
- 순차적으로 데이터를 접근하는 것이 가능하다.(동일)
- 다음 데이터를 접근(조회)하기 위해서는
Next pointer를 조회하면서 순회해야만 한다.
(시간복잡도 O(n)) - 연결리스트에 데이터를 삽입한다면, 삽입하려는 위치의
Next pointer만 조정해주면 되기 때문에,
링크를 조절하는 작업을 1번만 해주면된다.
(시간복잡도 O(1))
배열이 초기에 정적으로 메모리를 많이 잡는 단점때문에 연결리스트가 나왔다는데?
근데, JavaScript에서는 이미 동적으로 배열을 할당하는 것으로 알고 있다.
array[5]이런 식으로 선언하는 것이 아니라 그냥 배열 객체를 변수에 할당하고,push나unshift메소드를 통해서 데이터를 삽입하면 자동으로 그 크기에 맞는 배열(동적할당)이 된다. 그건 뭐 언어마다 다른 특성이겠지만 굳이 이것에 한해서는 JS에서 얘기하는 것이 의미있나 싶다. 하지만 자료구조의 탄생기원정도는 알고 있는게 개꿀딱이니까 알고 있도록 해야겠다.
"탐색과 정렬"을 자주한다면 "배열"을 쓰는게 낫고,
"추가와 삭제"가 많다면 "연결 리스트"쓰는게 낫다.
결론적으로 말하면, 연결리스트는 보관용 데이터에 쓰거나 state 변화를 history로 가지고 있으면서 current에 반영할 수 있는 상황에서 사용하는 것이 낫다. 대부분의 상황에서 배열이 나은듯.
일상생활에서 사용되는 linked list?
일단 이게 어디에 사용되는지보다 어떤 방식의 데이터인지 이해하기 위해선 일상에서의 이런 비슷한 사례가 있는지 생각해봤다. 이걸 뭐 코드로 보고 확실히 이해하는 것보다 이게 어떤 식으로 굴러가는지 컨셉을 이해하는것이 오히려 중요하다는 생각이 들기 때문이다.
유명 맛집 웨이팅
예를 들어 내가 유명 맛집에 웨이팅을 하고 있다고 생각해보자. 나는 일행인 친구 넷과 와서 4명이 같이 들어갈 자리가 필요한데, 내 팀 바로 뒤에 2명인 팀이 있다. 2명인 좌석이 먼저 생겨서 내 뒤에 팀이 먼저 들어가고 웨이팅 줄은 그대로 유지된다. 여기서 이해해야될 부분은 갑작스레 다른 팀이 끼어들어도 웨이팅 줄이 흩어지지 않고 유지되고 있다는 점이다. 중간에 끼워넣어도 순서는 그대로 유지되고 바뀌는 것이 없다.(물론 내 순서는 밀렸지만 기다리고 있다는 사실은 변하지 않았다.)
웹페이지 prev, next, 포토샵 histroy, 음악플레이어 플레이리스트
이전페이지로 돌아가거나, 다음페이지로 넘어가거나 하는 것들이 결국엔 방문 history를 buffer에 남겨두고 왔다리 갔다리하면서 페이지를 조회할 수 있다. 포토샵에서 사용하는 history도 똑같고, 음악플레이어에서 플레이리스트도 동일하다. 굳이 명확히 개념적으로 이야기하자면, 앞선 두개는 순서가 바뀔 수가 없으니 스택에 가깝고, 플레이리스트가 제일 비슷한거같다. 중간에 음악을 끼워넣는다고해도 순서에서 변하는게 없고 데이터만 바꿔끼워넣는 것에 가깝기 때문이다.
연결리스트의 특징
- 연속되는 노드들이 포인터(주소)로 연결되어 있다. (like 비엔나 소세지)
- 마지막 노드에는 null값이 들어간다.
- 프로그램이 수행되는 동안 메모리가 동적으로 할당되고 해제된다.(JS에선 배열도 마찬가지)
- 메모리 공간 낭비는 적지만, 포인터 메모리가 추가로 필요함
- 배열에 비해 데이터 추가/삽입이 빠르다.
- 모든 연결리스트는 순차적으로 탐색하지 않으면 요소 접근이 불가능. (like 헨젤과 그레텔)
- 데이터를 추가하는건 인스턴스임.
- 링크를 끊으면 데이터가 삭제되므로 head에서 노드를 전체 삭제하고 싶으면,대가리만 날리면 된다.
연결리스트의 종류
일방향 연결 리스트(Singly linked list)
위에서부터 쭉 얘기했던 연결리스트다. 여기는 노드에 있는 포인터(Next), 다음 노드를 가리키는 링크가 한 개인 연결리스트다. 이 리스트는 노드 하나에 포인터 데이터가 4바이트(address)만 차지해서 이중 연결 리스트보다 데이터를 아낄 수 있다. 얘는 뒤로 못 돌아가서 그냥 쭉 앞으로만 간다. like 스윙스
이중 연결 리스트(Doubly linked list)
노드에 하나만 달리니까 뒤로 갈 수가 없어서 포인터를 두 개(Next, Pre)로 두개로 앞 뒤로 포인터로 가리킨다. 어디로든 갈 수 있다. 대신에 포인터가 두개니까 데이터도 두배로 더 잡힌다. (4 * 2 = 8 바이트)
환형 연결 리스트(Circular linked list)
연결리스트에 head와 tail이 붙여져 있어서, 원처럼 회귀하는 리스트다. tail이 null을 가리키고있는 것이 아니라 다시 head를 가리킨다. 일방향 리스트에서는 끝까지 가면 null을 볼 수 있지만 환형은 재 순회가 가능한 구조를 가지고 있다.
연결리스트 코드로 구현해보자!
linked list와 node의 properties
linkedList.head
리스트의 첫번째 node
linkedList.tail
리스트의 마지막 node
linkedList.length
리스트에 총 몇개의 node가 있는지를 나타낸다.
node.next
다음 노드를 가리키는 next pointer
tail의 포인터는 null을 가르킨다.
linked list의 method
메소드야 목적에 따라서 달라질 수 있지만 필수적이고 중요한 것들만 적어본다.
linkedList.append()
list의 마지막에 추가해준다
linkedList.prepend()
list의 처음에 넣어준다.
linkedList.remove(data)
data를 삭제한다.
linkedList.removeAt(index)
해당 index에 있는 데이터 node를 삭제한다.
linkedList.removeHead()
list의 첫번째 node를 지워주고 그 값을 리턴해준다.
linkedList.removeTail()
list의 마지막 node를 지워주고 그 값을 리턴해준다.
linkedList.contains(data)
전달받은 data가 linked list에 있는지의 여부를 boolean값으로 리턴해준다.
linkedList.search(data)
data라는 값을 가진 node가 있으면 해당 노드를 리턴해준다
linkedList.inserAt(data, index)
list의 해당 index자리에 data를 넣어준다.
linkedList.size
linked list가 가지고 있는 총 데이터 개수를 반환한다.
linkedList.isEmpty
데이터의 존재여부에 따라 Boolean값은 반환한다.
도전! linkedList를 수도코드와 코드로 적어보자
ECMAScript6
class Node{
constructor(data){
this.data = data;
this.next = null;
}
}
class linkedList{
constructor(){
this.head = null; //응 아무것도 안가리켜
this.tail = null; //응 아무것도 안가리켜
this.length = 0; //응 0이야 없어서
}
append(value){
//list의 마지막에 추가해준다.
//만약에 현재 head가 없으면
//head와 tail에 같은 애를 붙여주고,
//length를 1늘림
//만약에 head가 있으면 tail에 붙여주고,
//length를 1늘림
}
prepend(value)
//list의 처음에 넣어준다.
//만약에 head가 없으면, append(value)
//만약 있으면, head로 next로 넣어주고,
//head로 바꿔줌
}
remove(data){
//data에 해당되는 노드를 삭제 해준다.
//
}
removeAt(index){
//해당 index에 있는 데이터 node를 삭제한다.
}
removeHead(){
//list의 첫번째 node를 지워주고 그 값을 리턴해준다.
}
removeTail(){
//list의 마지막 node를 지워주고 그 값을 리턴해준다.
}
contains(data){
//전달받은 data가 linked list에 있는지의 여부를 boolean값으로 리턴해준다.
}
search(data){
//data라는 값을 가진 node가 있으면 해당 노드를 리턴해준다
}
inserAt(data, index){
//list의 해당 index자리에 data를 넣어준다.
}
size(){
//linked list가 가지고 있는 총 데이터 개수(length property)를 리턴한다.
}
isEmpty(){
//데이터의 존재 여부에 따라 Boolean값은 반환한다.
}
> 이건 나중에 시간될때 다시오자. 2021년 4월 24일(토)
