[자바스크립트] 연결리스트

구현한 연결리스트의 ADT

1. 삽입

2. 삭제

3. 존재유무 

시간복잡도

- 정렬하지 않는 경우

삽입 : O(1) , 삭제 : O(N), 조회 : O(N)

- 정렬하는 경우

삽입 : O(N), 삭제 : O(1), 조회 : O(N)

function Node(data)
{
    this.data =data;
    this.next = null;
}


function LinkedList()
{
    this._length = 0;
    this._head = new Node('dummy');
    this._tail = this._head;
    this._before = null;
    this._cur = null;

}

LinkedList.prototype.append = function(data)
{   

    var node =new Node(data);
    this._tail.next =node;
    this._tail = node;

    this._length++;
}

LinkedList.prototype.search = function(data)
{   
var cur =this._head;
var before = cur;
for(var i=0;i<this._length;i++)
{
    cur = cur.next
    if(cur.data === data)
    {
        return 'Exist'
    }
}

return 'No Data'

}

LinkedList.prototype.delete = function(data)
{  

var cur =this._head;
var before;

for(var i=0;i<this._length;i++)
{
    before = cur;
    cur = cur.next

    if(cur.data === data)
    {
        before.next = cur.next
        cur = null;
        return 'Deleted'
    }


}

return 'No Data'

}

var linkedlist =new LinkedList()
linkedlist.append(4)
linkedlist.append(8)

var result = linkedlist.search(5)
console.log(result)

var result = linkedlist.delete(4)
console.log(result)
console.log(linkedlist)