js单向链表的具体实现实例


function linkNode(_key, _value)
{
    /// <summary>
    /// 链表类的节点类
    /// </summary>
    this.Key = _key;
    this.Value = _value;
    this.next = null;
}
function Link()
{
    /// <summary>
    /// 创建一个链表类
    /// </summary>
    this.root = new linkNode(null, null); //root永远是个空节点
    this.end = this.root;
}
Link.prototype =
{
    count: 0,
    value: function (_key)
    {
        /// <summary>
        /// 根据key的值来获取value值
        /// </summary>
        /// <param type="String">
        /// key的值
        /// </param>
        /// <returns type="Object">
        /// 对应的value的值
        /// </returns>
        var i = this.root;
        while (Boolean(i = i.next))
        {
            if (i.Key == _key)
                return i.Value;
        }
    },
    add: function (_key, _value)
    {
        /// <summary>
        /// 往链表的尾部中加入一个节点
        /// </summary>
        /// <param type="String">
        /// key的值
        /// </param>
        /// <param type="Object">
        /// value的值
        /// </param>
        /// <returns type="Object">
        /// 返回新增加的value的值
        /// </returns>
        var i = this.root;
        while (Boolean(i = i.next))
        {
            if (i.Key == _key)
                return i.Value = _value;
        }
        var node = new linkNode(_key, _value);
        if (this.count == 0)
            this.root.next = node;
        else
            this.end.next = node;
        this.end = node;
        this.count++;
        return _value;
    },
    insert: function (_key, node)
    {
        /// <summary>
        /// 从链表类的某节点之后插入新节点node.
        /// </summary>
        /// <param type="String">
        /// 在键值等于_key的元素之后插入
        /// </param>
        /// <param type="Object">
        /// 要插入的元素
        /// </param>
        var i = this.root;
        while (Boolean(i = i.next))
        {
            if (i.Key == _key)
            {
                var tmp = i.next;
                i.next = node;
                node.next = tmp;
                break;
            }
        }
    },
    insertBefore: function (_key, node)
    {
        /// <summary>
        /// 从链表类的某节点之后插入新节点node.
        /// </summary>
        /// <param type="String">
        /// 在键值等于_key的元素之后插入
        /// </param>
        /// <param type="Object">
        /// 要插入的元素
        /// </param>
        var i = this.root;
        while (Boolean(i = i.next))
        {
            if (i.next.Key == _key)
            {
                var tmp = i.next;
                i.next = node;
                node.next = tmp;
                break;
            }
        }
    },
    remove: function (_key)
    {
        /// <summary>
        /// 从链表类中移除一个key
        /// </summary>
        /// <param type="String">
        /// key的值
        /// </param>
        var i = this.root;
        do
        {
            if (i.next.Key == _key)
            {
                if (i.next.next == null)
                    this.end = i;
                i.next = i.next.next;

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/wdggpf.html