LinkedList | 연결리스트
Edit on GitHub연결 리스트는 동적인 자료 구조라서 필요할 떄마다 원소를 추가/삭제 할 수 있고 크기가 계속 변한다.
배열은 인덱스만 있으면 간단히 접근할 수 있지만 배열의 처음과 중간에서 원소를 넣고 뺴려면 다른 원소들까지 옮겨야 하므로
비싼 연산을 수반한다는 단점이 있다.
연결 리스트는 원소를 배열처럼 차례대로 저장하지만 원소들이 메모리상에 연속적으로 위치하지 않는다는 점이 다르다.
각 원소는 원소 자신과 다음 원소를 가리키는 참조 정보가 포한된 노드로 구성된다.
연결 리스트는 원소 추가/삭제 시 다른 원소들을 이동하지 않아도 된다는 점에서 배열보다 낫다.
배열은 측정 원소에 인덱스로 바로 접근할 수 있는 반면, 연결 리스트에서는 원소를 찾을 떄까지 처음부터 루프를 반복해야 한다.
연결 리스트 만들기
function LinkedList() {var Node = function(element) {this.element = element;this.next = null;};var length = 0;var head = null;this.append = function(element) {};this.insert = function(position, element) {};this.removeAt = function(position) {};this.remove = function(element) {};this.indexOf = function(element) {};this.isEmpty = function() {};this.size = function() {};this.toString = function() {};this.print = function() {};}
연결 리스트에 추가되는 원소가 바로 Node이다. element가 바로 원소에 해당되며, next 프로퍼티는 다음 노드를 가리키는 포인터이다.
length는 연결 리스트에 담긴 원소의 개수이다.
head는 연결이 시작되는 지점을 참조한다.
append() : 리스트의 맨 끝에 원소를 추가한다. insert() : 해당 위치에 원소를 추가한다. remove() : 원소를 삭제한다. indexOf() : 해당 원소의 인덱스를 반환한다. 존재하지 않을 경우 결과 값은 -1이다. removeAt() : 해당 위치에 있는 원소를 삭제한다. isEmpty() : 원소가 하나도 없다면 true, 그 외엔 false를 반환한다. size() : 원소 개수를 반환 toString() : 연결 리스트는 원소를 Node에 담아두기 때문에 원소의 값만을 출력하려면 toString 메서드를 재정의 해야한다.
리스트 끝에 원소 추가
추가 할때는 빈 연결 리스트인지 에 따라 경우를 고려해야한다.
this.append = function() {var node = new Node(element),current;if (head === null) {head = node;} else {current = head;while (current.next) {current = current.next;}current.next = node;}length++;};
리스트가 비어 있다면 head가 null이다.
head가 null이면 리스트에 원소를 추가하고 head가 추가한 node를 가리키면 된다.
그럼 node.next는 자동으로 null이 될 것이다.
이미 리스트에 원소가 들어 있다면 먼저 리스트의 마지막 원소를 찾아야 한다.
마지막 원소를 찾을 때까지 루프를 순회한다. 리스트의 현재 원소는 current에 담아두고 current.next가 null이 되는 지점에서 루프를 끝낸다.
이때 current가 마지막 원소 이므로 current.next를 새로 추가한 원소를 가리키게 된다.
나중에 리스트 크기를 참조할 수 있으니 length 하나 증가시킨다.
원소 삭제
삭제하려는 원소가 리스트의 첫 번쨰 원소인지 아닌지를 생각해야 한다.
remove 메서드는 원소의 위치를 기준으로 삭제하는 메서드와 원소의 값을 기준으로 삭제하는 메서드 두가지 이다.
원소의 위치를 기준으로 삭제하는 메서드를 만든다.
this.remove = function(position) {if (position > -1 && position < length) {var current = head,prev,index = 0;if (position === 0) {head = current.next;} else {while (index++ < position) {prev = current;current = current.next;}prev.next = current.next;}length--;return current.element;} else {return null;}};
삭제할 원소의 위치 값이 유효한지를 판별하는데 위치값은 0 에서 리스트 크기 사이의 값이여야 한다.
유효하지 않으면 null을 반환한다.
첫 번째 원소를 삭제하려면 우선 head가 그 다음원소를 가리키게 바꾸면 된다.
첫 번쨰 원소는 current 변수가 참조하므로 head를 current.next로 바꾸기만 하면 첫 번쨰 원소는 지워진다.
리스트의 마지막, 또는 중간에 위치한 원소를 삭제하는 경우를 보자.
리스트를 원하는 위치까지 루프를 돌려야 하는데, 루프문 내에서 current는 항상 리스트의 현재 원소를 가리키는 변수다.
그리고 현재 원소의 바로 이전 원소는 prev를 가리킨다.
그러므로 리스트에서 현재 원소를 삭제하려면 prev.next가 current.next를 가리키게 하면 된다.
마지막 원소일 경우 while 루프를 벗어나면 current 변수는 마지막 원소에 해당하고 current.next의 값은 null이다.
또한 prev가 가리키닌 원소에서 prev.next는 바로 current를 가리키고 있다.
따라서 prev.next를 current.next로 수정하면 current가 삭제되는 것과 같다.
중간에 있는 원소도 동일하다.
임의의 위치에 원소 삽입하기
this.insert = function(position, element) {if (position > -1 && position <= length) {var node = new Node(element),current = head,prev,index = 0;if (position === 0) {node.next = current;head = node;} else {while (index++ < position) {prev = current;current = current.next;}node.next = current;prev.next = node;}length++;return true;} else {return false;}};
항상 인덱스가 개입되면 범위 체크는 필수다. 범위를 벗어나면 false를 반환하여 아무것도 추가되지 않았음을 분명히 한다.
리스트의 맨 앞에 원소를 추가할 때 current는 리스트의 첫 번쨰 원소를 가리키는 변수 이므로 head는 current이다.
node.next를 current로 바꾸고 head를 node로 바꾸면 리스트의 첫 번쨰 위치에 원소가 삽입된다.
원소의 중간이나 끝에 추가하는 경우에는 원하는 위치까지 루프를 반복한다.
루프를 벗어날 때 current는 삽입할 위치 바로 다음 원소, prev는 이전 원소를 가리킬 것이다.
이 떄 삽입할 원소와 current 원소를 연결하고 prev와 current 사이의 연결을 바꾸면 된다.
즉 prev.next가 node를 바라보면 된다.
그 밖의 메서드 구현
toString 메서드
this.toString = function() {var current = head,string = "";while (current) {string += current.element;current = current.next;}return string;};
리스트의 모든 원소를 순회하기 위해 head를 시작점으로 current 변수를 인덱스 삼아 루프문을 실행한다.
그 전에 결과를 담아둘 변수를 초기화한다.
원소별로 순회할 때 current 변수로 원소의 존재 여부를 체크한다. 그 다음 원소 값을 추출해 string에 이어붙이고 다음 원소를 순회한다.
indexOf 메서드
원소 값을 인자로 받아 리스트에서 해당 원소의 인덱스를 반환한다. 없는 원소라면 -1을 반환한다.
this.indexOf = function(element) {var current = head,index = -1;while (current) {if (element === current.element) {return index;}index++;currnet = current.next;}return -1;};
리스트 순회하기 전에 current를 head, 리스트의 첫 번째 원소로 초기화 한다.
원소를 차례로 순회하면서, 인자로 받은 원소 값과 일치하는지본다.
일치하면 위치를 반환하고, 다르면 index를 하나씩 증가시키고 다음 노드를 뒤진다.
리스트가 비어 있거나 리스트 끝에 도달하면 루프는 끝난다. 발견된 원소가 없으면 결과는 -1이다.
this.remove = function(element) {var index = this.indexOf(element);return this.removeAt(index);};
원소의 값만 넘기면 인덱스를 찾을 수 있고 이렇게 찾은 인덱스를 다시 removeAt 메서드로 넘겨주면 해당 원소를 삭제할 수 있다.
isEmpty, size, getHead 메서드
isEmpty는 리스트에 원소가 하나라도 있으면 true 없으면 false를 반환한다.
size는 리스트의 크기를 반환한다. length는 내부에서만 쓰는 변수이다.
head는 LinkedList의 프라이빗 변수이다. 인스턴스 밖에서도 리스트를 반복시킬때 첫 번쨰 원소를 참조할 필요는 있다.
this.isEmpty = function() {return length === 0;};this.size = function() {return length;};this.getHead = function() {return head;};
이중 연결 리스트
연결 리스트는 다음 노드의 연결 정보만 갖고 있지만 이중 연결 리스트는 다음 노드와 이전 노드 2개의 연결 정보를 가지고 있다.
function DoublyLinkedList() {var Node = function(element) {this.element = element;this.next = null;this.prev = null;};var length = 0;var head = null;var tail = null;}
이중 연결 리스트에서는 처음에서 끝, 끝에서 처음, 양방향으로 리스트 순회가 가능하다. 어떤 노드의 이전, 이후 노드를 찾아 갈수 있기 떄문이다.
한 방향으로만 링크된 연결 리스트는 순회 시 원소를 찾지 못하면 다시 맨 처음으로 돌아가야 한다.
임의의 위치에 원소 삽입
연결 리스트와 방법은 비슷하다. 차이점은 이중 연결 리스트는 next와 prev 링크가 2개라는 점이다.
this.insert = function(position, element) {if (position >= 0 && position <= length) {var node = new Node(element),current = head,prev,index = 0;if (postion === 0) {if (!head) {head = node;tail = node;} else {node.next = current;current.prev = node;head = node;}} else if (position === length) {current = tail;current.next = node;node.prev = current;tail = node;} else {while (index++ < position) {prev = current;current = current.next;}node.next = current;prev.next = node;current.prev = node;node.prev = prev;}length++;return true;} else {return false;}};
리스트의 첫 번쨰 위치에 삽입하는 경우 리스트가 비어 있으면 head,tail이 삽입할 노드를 가리키게 하면 되고,
그 외에는 current에 첫 번째 원소를 담는다.
연결 리스트와 마찬가지로 node.next를 current로 head를 node로 바꿔주면 node는 첫 번쨰 원소가 된다.
이전원소에 대한 포인터 세팅 작업이 추가된 점이 다르다.
current.prev는 이제 null이 아닌 node를 가리키고 node.prev는 처음부터 null 이니 그냥 두면 된다.
맨 끝에 새 원소를 추가하는 경우는 마지막 원소를 가리키는 tail 변수를 사용해 current 에 마지막 원소를 넣고 node.prev를 current로 세팅한다.
current.next를 node로 바꾼다. 그리고 tail 자리는 이제 current가 아닌 node이다.
임의의 위치에 삽입하는 경우 원하는 위치에 도달할 떄까지 루프를 반복한 뒤 current와 prev 원소 사이에 node를 끼워 넣는다.
먼저 node.next를 current로 prev.next를 node로 바꾸어 링크가 깨지지 않게 한다.
그 다음은 current.prev를 node로 node.prev를 prev로 바꾼다.
원소 삭제
원소 삭제도 연결 리스트와 유사하다. 이전 원소를 가리키는 포인터가 하나 더 있는 점이 다르다.
this.remove = function(position) {if (position > -1 && position < length) {var current = head,prev,index = 0;if (position === 0) {head = current.next;if (length === 1) {tail = null;} else {head.prev = null;}} else if (position === length - 1) {current = tail;tail = current.prev;tail.next = null;} else {while (index++ < position) {prev = current;current = current.next;}prev.next = current.next;current.next.prev = prev;}length--;return current.element;} else {return null;}};
첫 번쨰 원소를 삭제 할때 current는 첫 번째 원소이고 이 원소를 삭제할때는 current가 아닌 current.next를 head로 바꾼다.
그리고 head.prev를 null로 바꾼다. 이렇게 삭제한 원소가 이 리스트의 하나뿐인 원소라면 tail은 null이 된다.
마지막 원소를 삭제 할때는 마지막 원소는 tail이 가리키고 있으므로 current를 tail로 바꾸고 tail을 current.prev로 업데이트한다.
두 번쨰 원소이므로 tail.next는 null로 수정한다.
특정 위치의 원소를 삭제할때는 원하는 위치를 얻기 위해 루프를 통해 삭제할 원소를 current로 받는다.
그리고 prev.next는 current.next로 current.next.prev는 prev로 바꿔주면 원소의 앞뒤 연결이 끊긴다.
환영 연결리스트
환형 연결 리스트는 단방향 또는 양방향 참조 정보를 갖는다.
마지막 원소의 next가 null이 아닌 첫 번째 원소를 가리킨다.
function CircularLinkedList() {var node = function Node(element) {this.element = element;this.next = null;};var length = 0;var head = null;this.append = function(element) {var node = new Node(element),current;if (head === null) {head = node;} else {current = head;while (current.next !== head) {current = current.next;}current.next = node;}node.next = head;length++;};this.insert = function(position, element) {if (position > -1 && position <= length) {var node = new Node(element),current = head,prev,index = 0;if (position === 0) {node.next = current;while (current.next !== head) {current = current.next;}head = node;current.next = head;} else {while (index++ < position) {prev = current;current = current.next;}node.next = current;prev.next = node;if (node.next === null) {node.next = head;}}length++;return true;} else {return false;}};this.removeAt = function(position) {if (position > -1 && position < length) {var current = head,prev,index = 0;if (position === 0) {while (current.next !== head) {current = current.next;}head = head.next;current.next = head;} else {while (index++ < position) {prev = current;current = current.next;}prev.next = current.next;}length--;return current.element;} else {return null;}};this.remove = function(element) {var index = this.indexOf(element);return this.removeAt(index);};this.indexOf = function(element) {var current = head,index = -1;if (current.element === element) {return 0;}index++;while (current.next !== head) {if (current.element === element) {return index;}index++;current = current.next;}if (current.element === element) {return index;}return -1;};}
이중 환영 연결 리스트는 tail.next가 head를 head.prev가 tail을 상호 참조하는 구조로 되어 있다.
정리
배열 과 달리 다른 원소를 이동하지 않고 원소를 쉽게 추가/삭제 할수 있다
따라서 많은 원소를 추가/삭제 해야할 경우 배열보다는 연결 리스트가 더 좋다.