이중 연결리스트
#
Find similar titles
-
최초 작성자
jipark-intern@insilicogen.com
- 최근 업데이트
Structured data
- Category
- Programming
이중 연결리스트(Doubly Linked List) #
정의 #
각 리스트의 노드가 이전노드, 다음노드를 가리키는 포인터가 존재한다. 따라서 노드의 이동이 자유로운 장점이 있다. 하지만 노드의 추가/삭제 시 관리 해야할 요소가 많아지는 단점이 있다.
배열과 차이점 #
이중연결리스트 데이터 삽입 구조
배열(Array)은 구조가 단순하기 때문에 관리가 용이하다. 하지만 배열의 중간의 Index가 삭제되어 데이터가 없게 된다 그 배열 Index는 특별한 처리를 하지 않는한 null이 된다. 따라서 배열은 쓸데없는 메모리 공간을 차지할 수 있다. 하지만 이중 연결리스트는 중간의 데이터가 삭제되면 데이터만 사라지고 삭제된 노드의 이전 노드가 삭제된 다음 노드를 가리키는 것으로 수정되기 때문에 메모리 공간을 낭비할 필요가 없어진다.
간단한 구현(java) #
public class DoublyLinkedList {
private Node header;
private int size;
public DoublyLinkedList(){
header = new Node(null);
size=0;
}
//node의 초기상태
//처음 노드는 이전 노드(previousNode)가 null이되며
//마지막 노드는 다음 노드(nextNode)가 null이 된다.
private class Node{
private Object data;
private Node previousNode;
private Node nextNode;
Node(Object data){
this.data = data;
this.previousNode = null;
this.nextNode = null;
}
}
}
//데이터 탐색
/*
이중 연결 리스트는 지정한 위치의 노드를 꺼내기 위해서 index 값이 데이터의 앞부분에 있을 경우(index < size/2) 처음 노드부터 순방향으로 탐색을 하고 index 값이 데이터의 뒷부분에 있을 경우 (index >= size/2) 마지막 노드부터 역방향으로 탐색을 시도한다.
평균적으로 순방향의 경우나 역방향의 경우 모두 데이터수/4 만큼의 순차접근을 처리하므로 전체적인 효율은 단순 연결 리스트의 2배가 된다.
*/
public Object get(int index){
return getNode(index).data;
}
private Node getNode(int index){
if(index < 0 || index > size){
throw new IndexOutOfBoundsException("Index : "+index+", Size : " + size);
}
Node node = header;
// index 가 리스트 size의 중간 앞이면 순차적으로 탐색한다.
if(index < (size/2)){
for(int i =0; i<=index; i++){
node = node.nextNode;
}
}else{
// index가 리스트 size의 중간보다 뒤면 뒤에서부터 탐색한다.
for(int i = size; i > index; i--){
node = node.previousNode;
}
}
return node;
}
//데이터 삽입
public void addFirst(Object data){
// 데이터를 담은 새로운 노드 생성
Node newNode = new Node(data);
// 새로운 노드가 다음 노드로 첫번째 노드를 가리킨다.
newNode.nextNode = header.nextNode;
// 리스트가 비어있지 않으면
if(header.nextNode != null){
// 첫 노드가 자신의 앞 노드로 새로운 노드를 가리킨다.
header.nextNode.previousNode = newNode;
}else{ // 리스트가 비어있으면
// 헤더가 마지막 노드를 새로운 노드로 가리키도록 한다.
header.previousNode = newNode;
}
// 헤더가 첫번째 노드로 새로운 노드를 가리키도록 한다.
header.nextNode = newNode;
size++;
}
//데이터 삭제
public Object removeFirst(){
// 첫번째 노드를 가져온다.
Node firstNode = getNode(0);
// 헤더가 첫 노드로 두번째 노드를 가리킨다.
header.nextNode = firstNode.nextNode;
// 리스트가 비어있지 않을 때
if(header.nextNode != null){
// 두번째 노드가 가리키는 앞 노드는 없다.
firstNode.nextNode.previousNode = null;
}else{ // 리스트가 비게 되면
// 헤더가 가리키는 마지막 노드가 없다.
header.previousNode = null;
}
size--;
// 첫번째 노드의 데이터를 반환
return firstNode.data;
}