Doubly linked list

linked list와 다른점 하나.

node에 이전 노드를 가리키는 포인터가 추가되었다.

 

 

포인트 2개

삽입 및 삭제가 용이. 삽입 또는 삭제 연산을 수행할 때, 해당 노드의 이전 노드와 다음 노드를 적절하게 연결하면 됨. 노드를 삽입하거나 삭제하는 작업이 단일 연결 리스트보다 간단하게 처리가능.

단일 연결 리스트에 비해 메모리 공간이 더 많이 사용됨. 각 노드마다 이전 노드와 다음 노드를 가리키는 두 개의 포인터가 추가로 필요하기 때문이다.

 

 

 

append

0(1)

public void append(int value){
        Node newNode = new Node(value);

        if(length == 0){
            head = newNode;
            tail = newNode;

        }else{
            //link new node to last node
            newNode.prev = tail;
            //link last node to new node
            tail.next = newNode;
            //set tail to point new node
            tail = newNode;
        }

        length++;

    }

 

---

 

removeLast

0(1)

나

public Node removeLast(){
	    if(length == 0) return null;
	   
	   
	   Node temp = tail;
	    if(length == 1){
	        head = null;
	        tail = null;
	    }else{
    	    Node prevTemp = temp.prev;
    	    tail.prev.next = null;
    	    tail.prev = null;
    	    tail = prevTemp;

	    }
	    
	    length--;
	    
	    return temp;
	    
	    
	}

 

답

public Node removeLast() {
        if(length == 0) return null;
        Node temp = tail;
        if (length == 1) {
            head = null;
            tail = null;
        } else {
            tail = tail.prev;
            tail.next = null;
            temp.prev = null;
        }
        length--;
        return temp;
    }

음.. 다 풀고나서 답을 보면 뭔가 ,, 내가 왜 저랬지? 생각하게 됨..ㅋㅋ 포인터에 아직 그렇게까진 안익숙한듯

 

 

---

Get

0(n)

prev이용해서 해야함.

 

public Node get(int index) {
        if (index < 0 || index >= length) return null;
        Node temp = head;
        if (index < length/2) {
            for (int i = 0; i < index; i++) {
                temp = temp.next;
            }
        } else {
            temp = tail;
						//index starts from 0 , so length - 1
            for (int i = length - 1; i > index; i--) {
                temp = temp.prev;
            }
        }
        return temp;
    }

 

--

insert

0(n)

나

public boolean insert(int index, int value){
	    if(index < 0 || index > length) return false;
	    if(index == 0 ){
	        prepend(value);
	        return true;
	    }
	    
	    if(index == length){
	        append(value);
	        return true;
	    }
	    
	    Node newNode = new Node(value);
	    Node prev = get(index - 1);
	    Node temp = prev.next;
	    prev.next = newNode;
	    newNode.prev = prev;
	    newNode.next = temp;
	    temp.prev = newNode;
	    
	    length++;
	    
	    return true;
	    
	}

답

public boolean insert(int index, int value){
	    if(index < 0 || index > length) return false;
	    if(index == 0 ){
	        prepend(value);
	        return true;
	    }
	    
	    if(index == length){
	        append(value);
	        return true;
	    }
	    
	    Node newNode = new Node(value);
	    Node prev = get(index - 1);
	    Node temp = prev.next;
	    prev.next = newNode;
	    newNode.prev = prev;
	    newNode.next = temp;
	    temp.prev = newNode;
	    
	    length++;
	    
	    return true;
	    
	}

변수명 after로 하면 될걸 왜 temp로 했지.?

 

---

 

---