当前位置:首页 > 开发 > 编程语言 > Java > 正文

java 实现自定义链表

发表于: 2015-06-06   作者:CrazyMizzz   来源:转载   浏览:
摘要: 1.链表结构   链表是链式的结构 2.链表的组成    链表是由头节点,中间节点和尾节点组成    节点是由两个部分组成:       1.数据域       2.引用域 3.链表的实现 &nbs
1.链表结构

  链表是链式的结构


2.链表的组成

   链表是由头节点,中间节点和尾节点组成

   节点是由两个部分组成:

      1.数据域
      2.引用域


3.链表的实现

   Node{

      数据域

      引用域

   }

   MyLinkedList{

      记录元素总数的属性

      头节点属性

      head;

      尾节点属性

      trail;

     }
下面上代码


public class DoubleLinkedList{
	private static class Node {
		Object value;
		Node prev = this;
		Node next = this;

		Node(Object v) {
			value = v;
		}

		public String toString() {
			return value.toString();
		}
	}

	private Node head = new Node(null);
	// 头节点
	private int size;

	// 链表大小
	// 以下是接口方法
	public boolean addFirst(Object o) {
		addAfter(new Node(o), head);
		return true;
	}

	public boolean addLast(Object o) {
		addBefore(new Node(o), head);
		return true;
	}

	public boolean add(Object o) {
		return addLast(o);
	}

	public boolean add(int index, Object o) {
		addBefore(new Node(o), getNode(index));
		return true;
	}
	
	public boolean revise(int index, Object o) {
		reviseNode(new Node(o), getNode(index));
		return true;
	}
	
	public boolean remove(int index) {
		removeNode(getNode(index));
		return true;
	}

	public boolean removeFirst() {
		removeNode(head.next);
		return true;
	}

	public boolean removeLast() {
		removeNode(head.prev);
		return true;
	}

	public Object get(int index) {
		return getNode(index).value;
	}

	public int size() {
		return size;
	}

	public String toString() {
		StringBuffer s = new StringBuffer();
		Node node = head;
		for (int i = 0; i < size; i++) {
			node = node.next;
			if (i > 0)
				s.append("   ");
			s.append(node.value);
		}
		return s.toString();
	}

	private Node getNode(int index) {
		if (index < 0 || index >= size)
			System.out.println("错误");
		Node node = head.next;
		for (int i = 0; i < index; i++)
			node = node.next;
		return node;
	}

	private void addBefore(Node newNode, Node node) {
		newNode.next = node;
		newNode.prev = node.prev;
		newNode.next.prev = newNode;
		newNode.prev.next = newNode;
		size++;
	}
	
	private void reviseNode(Node newNode, Node node) {
		newNode.next = node.next;
		newNode.prev = node.prev;
		newNode.next.prev = newNode;
		newNode.prev.next = newNode;
	}

	private void addAfter(Node newNode, Node node) {
		newNode.prev = node;
		newNode.next = node.next;
		newNode.next.prev = newNode;
		newNode.prev.next = newNode;
		size++;
	}

	private void removeNode(Node node) {
		node.prev.next = node.next;
		node.next.prev = node.prev;
		node.prev = null;
		node.next = null;
		size--;
	}
}

java 实现自定义链表

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
public class DoublyLinkList { private class Data{ private Object obj; private Data left = nul
单链表优点:1.不需要预先给出元素个数。 2.单链表插入删除时不需要移动数据元素。 单链表缺点:1.
  最近被问到链表,是一个朋友和我讨论Java的时候说的。说实话,我学习编程的近一年时间里,学到
单链表: insertFirst:在表头插入一个新的链接点,时间复杂度为O(1) deleteFirst:删除表头的链接
单链表翻转比如有如下链表: 需要按照C B A 输出,我们可以有好几种方法: package org.andy.test;
线性表的Java实现--链式存储(双向链表) 有了单向链表的基础,双向链表的实现就容易多了。 双向链
线性表的Java实现--链式存储(单向链表) 单向链表(单链表)是链表的一种,其特点是链表的链接方向
这几年一直做企业ERP基础架构,对于算法领域的知识使用的较少,前两天被他人问及链表如何实现,草草
欢迎讨论,转载请注明出处哦 前面一篇文章说明了线性表主要有三种结构:顺序表、单链表、双链表。
二叉链表存储的思想是让每个节点都记住它的左、右两个子节点,为每个节点增加left、right两个指针,
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号