JavaScript封装单向链表的示例代码

Elsa ·

更新时间:2024-11-15

· 831 次阅读

使用JavaScript封装单向链表：

1. 封装LinkList的类，用于表示我们的链表结构。

2. 在LinkList类中有一个Node类，用于封装每一个节点上的信息（data与next）。

3. 在链表中保存两个属性，一个是链表的长度，一个是链表中的第一个节点。

4.封装一些链表的常用方法：

append(element)：想列表尾部添加一个新的项； insert(position,element)：向列表的特定位置插入一个新的项； get(position)：获取对应位置的元素； indexOf(element)：返回元素在链表中的索引，如果链表中没有该元素则返回-1； update(position,element)：修改某个位置的元素； removeAt(postion)：从列表的特定位置移除一项； remove(element)：从列表中移除一项； isEmpty()：如果链表中不包含任何元素，返回true，否则返回false； size()：返回链表中包含元素的个数； toString()：输出链表元素的值；


<script type="text/javascript">
	function LinkList(){
		/* 节点类 */
		function Node(data){
			this.data = data
			this.next = null
		}
		this.head = null
		this.length = 0
		/* 追加方法 */
		LinkList.prototype.append = function(data){
			/* 创建新节点 */
			var newNode = new Node(data)
			if(this.length === 0){
				this.head = newNode
			}else{
				/* 找到最后一个节点 */
				var current = this.head
				while(current.next){
					current = current.next
				}
				current.next = newNode
			}
			this.length += 1
		}
		/* toString方法 */
		LinkList.prototype.toString = function(){
			var current = this.head
			var listString = ""
			while(current){
				listString += current.data +" "
				current = current.next
			}
			return listString
		}
		/* insert方法 */
		LinkList.prototype.insert = function(position,data){
			/* 对position进行越界判断 */
			if(position<0||position>this.length) return false
			var node = new Node(data)
			if(position == 0){
				node.next = this.head
				this.head = node
			}else{
				var index = 0
				var current = this.head
				var previous = null
				while(index++ < position){
					previous = current
					current = current.next
				}
				node.next = current
				previous.next = node
			}
			this.length += 1
			return true
		}
		/* get方法 */
		LinkList.prototype.get = function(position){
			/* 越界判断 */
			if(position<0 || position >= this.length) return null
			var current = this.head
			var index = 0
			while(index++ < position){
				current = current.next
			}
			return current.data
		}
		/* indexOf方法 */
		LinkList.prototype.indexOf = function(data){
			/* 定义变量 */
			var current = this.head
			var index = 0
			/* 开始查找 */
			while(current){
				if(current.data === data){
					return index
				}else{
					current = current.next
					index += 1
				}
			}
			return -1
		}
		/* update方法 */
		LinkList.prototype.update = function(position,data){
			/* 越界判断 */
			if(position<0 || position >= this.length) return false
			var current = this.head
			var index = 0
			while(index++ < position){
				current = current.next
			}
			/* 修改data */
			current.data = data
			return true
		}
		/* removeAt方法 */
		LinkList.prototype.removeAt = function(position){
			/* 越界判断 */
			if(position<0 || position >= this.length) return null
			var current = this.head
			if(position === 0){
				this.head = this.head.next
			}else{
				var index = 0
				var previous = null
				while(index++ < position){
					previous = current
					current = current.next
				}
				previous.next = current.next
			}
			this.length -= 1
			return current.data
		}
		/* remove */
		LinkList.prototype.remove = function(data){
			/* 根据data找位置 */
			var position = this.indexOf(data)
			return this.removeAt(position)
		}
		LinkList.prototype.isEmpty = function(){
			return this.length === 0
		}
		LinkList.prototype.size = function(){
			return this.length
		}
	}
	/* 测试 */
	var list = new LinkList()
	list.append('a')
	list.append('b')
	list.append('c')
	console.log(list.toString()) /* a b c */
	list.insert(3,'d')
	console.log(list.toString())/* a b c d */
	console.log(list.get(2)) /* c */
	console.log(list.indexOf('d')) /* 3 */
	list.update(1,'bbb')
	console.log(list.toString()) /* a bbb c d */
	console.log(list.removeAt(2)) /* c */
	console.log(list.toString())/* a bbb d */
	console.log(list.remove('a'))
	console.log(list.toString())/* bbb d */
	console.log(list.isEmpty()) /* false */
	console.log(list.size()) /* 2 */
</script>

以上就是JavaScript封装单向链表的示例代码的详细内容，更多关于JavaScript封装单向链表的资料请关注软件开发网其它相关文章！

单向链表示例链表 JavaScript

1024 个赞