- 浏览: 182765 次
- 性别:
- 来自: 自己输入城市...
文章分类
- 全部博客 (128)
- Java (13)
- Util (21)
- IO (1)
- Thread (4)
- Net (0)
- Design Patterns (0)
- Training (4)
- ----------------- (0)
- JS-1 (15)
- JS-3 (7)
- AJAX (3)
- AS (2)
- ------------------- (0)
- HTML (3)
- CSS (3)
- Art (15)
- -------------------- (0)
- RegExp (4)
- --------------------- (0)
- SQL (6)
- Servlet $ JSP (2)
- JDBC (2)
- ---------------------- (0)
- Bird (3)
- Setting (7)
- DL (4)
- PHP (4)
最新评论
-
durong11:
或者直接在函数的中加入:if(head.data.equals ...
我的Java单链表练习 -
durong11:
一种解释是:如果是从头结点insert 直接使用addFrom ...
我的Java单链表练习 -
老肥猴_vi:
谢谢。但是貌似insert函数( public boolean ...
我的Java单链表练习 -
niepeng880208:
支持
List转换成String数组 -
haohao-xuexi02:
EventHelp
幻灯片效果
■ 构造函数
每个构造函数都通过 this 来初始化链接域 prev 和 next.图⑴
■ 判断表空的条件
图⑴
■ addBefore 方法是 MyLinkedList 类的重要方法, 后面的很多方法都要依靠它来实现!图⑵
图⑵
■ addFirst方法就是靠addBefore来实现的!
因为
header.next = nd' -->图⑵
所以
curr = nd' --> addBefore()方法
因此
prevNode = curr.prev = h --> addBefore()方法
继续重复这四句话
newNode.prev = prevNode; ①
newNode.next = curr; ②
prevNode.next = newNode; ③
curr.prev = newNode; ④
图⑶
■ remove方法也很重要!
每个构造函数都通过 this 来初始化链接域 prev 和 next.图⑴
prev = this; next = this;
■ 判断表空的条件
public boolean isEmpty() { return (header.prev == header || header.next == header); }
图⑴
■ addBefore 方法是 MyLinkedList 类的重要方法, 后面的很多方法都要依靠它来实现!图⑵
private static <T> DNode<T> addBefore(DNode<T> curr, T item) { DNode<T> newNode, prevNode; newNode = new DNode<T>(item); prevNode = curr.prev; newNode.prev = prevNode; ① newNode.next = curr; ② prevNode.next = newNode; ③ curr.prev = newNode; ④ return newNode; }
图⑵
■ addFirst方法就是靠addBefore来实现的!
因为
header.next = nd' -->图⑵
所以
curr = nd' --> addBefore()方法
因此
prevNode = curr.prev = h --> addBefore()方法
继续重复这四句话
newNode.prev = prevNode; ①
newNode.next = curr; ②
prevNode.next = newNode; ③
curr.prev = newNode; ④
public void addFirst(T item) { addBefore(header.next, item); listSize++; }
图⑶
■ remove方法也很重要!
private void remove(DNode<T> curr) { if(curr.next == curr) return; DNode<T> prevNode = curr.prev, nextNode = curr.next; prevNode.next = nextNode; nextNode.prev= prevNode; }
package LinkedList; import java.util.Iterator; import java.util.ListIterator; import java.util.NoSuchElementException; public class MyLinkedList<T> { //************************************************************* private DNode<T> header; private int listSize; //************************************************************* public MyLinkedList() { header = new DNode<T>(); listSize = 0; } //************************************************************* private static class DNode<T> { T nodeValue; DNode<T> prev; DNode<T> next; public DNode() { // for header nodeValue = null; prev = this; // left next = this; // right } public DNode(T item) { nodeValue = item; prev = this; next = this; } } //************************************************************** public boolean isEmpty() { return (header.prev == header || header.next == header); } public int size() { return listSize; } //************************************************************** private DNode<T> addBefore(DNode<T> curr, T item) { DNode<T> newNode, prevNode; newNode = new DNode<T>(item); prevNode = curr.prev; newNode.prev = prevNode; newNode.next = curr; prevNode.next = newNode; curr.prev = newNode; return newNode; } public boolean add(T item) { addBefore(header, item); listSize++; return true; } public void addFirst(T item) { addBefore(header.next, item); listSize++; } public void addLast(T item) { addBefore(header, item); listSize++; } //************************************************************** private void remove(DNode<T> curr) { if(curr.next == curr) return; DNode<T> prevNode = curr.prev, nextNode = curr.next; prevNode.next = nextNode; nextNode.prev= prevNode; } public boolean remove(Object o) { for(DNode<T> p = header.next; p != header; p = p.next) { if(o.equals(p.nodeValue)) { remove(p); listSize--; return true; } } return false; } //************************************************************** public void printList() { for(DNode<T> p = header.next; p != header; p = p.next) System.out.println(p.nodeValue); } //************************************************************** private class MyIterator implements Iterator<T> { public DNode<T> nextNode = header.next; public DNode<T> lastReturned = header; public boolean hasNext() { return nextNode != header; } public T next() { if(nextNode == header) throw new NoSuchElementException(""); lastReturned = nextNode; nextNode = nextNode.next; return lastReturned.nodeValue; } public void remove() { if(lastReturned == header) throw new IllegalStateException(""); MyLinkedList.this.remove(lastReturned); lastReturned = header; listSize--; } } //************************************************************** private class MyListIterator extends MyIterator implements ListIterator<T> { private int nextIndex; MyListIterator(int index) { if(index < 0 || index > listSize) throw new IndexOutOfBoundsException(""); //如果index小于listSize/2,就从表头开始查找定位,否则就从表尾开始查找定位 if(index < (listSize >> 1)) { nextNode = header.next; for(nextIndex = 0; nextIndex < index; nextIndex++) nextNode = nextNode.next; }else { nextNode = header; for(nextIndex = listSize; nextIndex > index; nextIndex--) nextNode = nextNode.prev; } } public boolean hasPrevious() { return nextIndex != 0; //return nextNode.prev != header; } public T previous() { if (nextIndex == 0) throw new NoSuchElementException("no"); lastReturned = nextNode = nextNode.prev; nextIndex--; return lastReturned.nodeValue; } public void remove() { if(lastReturned == header) throw new IllegalStateException(""); MyLinkedList.this.remove(lastReturned); nextIndex--; listSize--; if(lastReturned == nextNode) nextNode = nextNode.next; lastReturned = header; } public void add(T item) { MyLinkedList.this.addBefore(nextNode, item); nextIndex++; listSize++; lastReturned = header; } public void set(T item) { if (lastReturned == header) throw new IllegalStateException(); lastReturned.nodeValue = item; } public int nextIndex() { return nextIndex; } public int previousIndex() { return nextIndex - 1; } } //************************************************************** public Iterator<T> iterator() { return new MyIterator(); } //************************************************************** public ListIterator<T> listIterator(int index) { return new MyListIterator(index); } //************************************************************** public static void main(String[] args) { MyLinkedList<String> t = new MyLinkedList<String>(); t.add("A"); t.add("B"); t.add("C"); t.add("D"); //t.remove("B"); //t.addFirst("AA"); //t.addLast("BB"); //t.printList(); /* Iterator<String> it = t.iterator(); while(it.hasNext()) System.out.println(it.next()); // A B C D */ ListIterator<String> it = t.listIterator(t.size()); while(it.hasPrevious()) { System.out.println(it.previous()); // D C B A } } }// MyLinkedList end~
发表评论
-
优先队列的实现
2008-05-11 05:00 938package Heap; import MyInter ... -
堆操作
2008-05-11 02:06 947Comparator接口 package MyInterfac ... -
HashSet 类的实现
2008-04-28 16:03 1163package Hash; import MyInter ... -
HashMap类的实现
2008-04-28 12:20 1507package Hash; import java.ut ... -
Hash类的实现
2008-04-27 15:10 792package Hash; import java.util ... -
散列表的设计-->线性探查法
2008-04-24 09:07 1890性能分析: 散列表中条目数的比例较小时,使用线性探查法的效率较 ... -
二叉排序树的TreeMap类设计
2008-04-23 23:29 1917Iterable接口 package MyInterface; ... -
java集合操作
2008-04-23 23:26 2993package Sets; import java.util ... -
二叉排序树的实现
2008-04-20 01:46 1640最适合用STree排序的是不可变类,不可变类的主要特征是它的对 ... -
InorderIterator类的实现
2008-04-07 08:41 931接口的定义: public interface MyItera ... -
BinaryTree遍历练习::表达式树
2008-04-05 14:35 1757package ExpressionTree; import ... -
二叉树遍历
2008-03-31 01:48 1057二叉树的高度 图(1) /**用后根遍历求二叉树的高度*/ ... -
有界队列
2008-03-26 00:14 972package Queue; import java.uti ... -
Stack练习:: 中缀-后缀表达式
2008-03-21 17:18 1745package Stack.Calculate; imp ... -
链式队列的实现
2008-03-21 17:05 1313package Queue; import java.u ... -
Stack练习:: 十进制正整数转化成二进制
2008-03-17 16:09 1243include "stdio.h" in ... -
顺序栈的实现
2008-03-14 00:16 1054package Stack; /** * 顺序栈的实现 ... -
我的Java单链表练习
2008-03-06 19:14 2997package LinkedList; /** * ... -
我的ArrayList实现
2008-03-04 21:26 1345package ArrayList; /** * < ... -
[转]数据结构 用Java实现单链表
2007-11-28 12:56 17162007-08-24 页面自动刷 ...
相关推荐
用java语言将双向链表和循环链表结合起来,数据结构吧课程设计的题目
用C++和Java实现带头节点的双向循环链表,要继承linearList类,并实现它的所有功能,另外,必须实现双向迭代器。 实现带头节点的双向循环链表,要具有以下的功能: 判断表是否为空,如果为空则返回true,不空返回...
//定义链表结构 NODE *inputint(void){ //输入超长整数,存入链表 } NODE *insert_after(NODE *u,int num){ //在u结点后插入一个新的NODE,其值为num } int compare(NODE *p,NODE *q){ //比较两个数的大小 } ...
数据结构-链表 JAVA语言实现,包含单向链表、双向链表、循环链表的遍历、删除和插入 详细介绍:http://blog.csdn.net/z740852294/article/details/77369439
酒吧里,一桌人(≥10)围在一起行酒令。酒令如下:先按照顺时针方向从1开始依此数数。若是数到7的倍数或者含有7这个数,则调转方向接着数。依此类推。请模拟此过程。
C++实现 数据结构与算法视频教程 01交换算法 02冒泡排序 03选择排序 04顺序排序 05折半排序 06递归算法 07递归折半查找 08算法_perm 09插入排序 10快速排序 11归并排序 12顺序栈 13顺序队列 14链表的基本概率 15...
里面有注释,很详细。 对于数据结构基础不是很好地朋友来说,有很大的帮助。
这是自己写的一个Java实现模拟数据结构中的LinkedList。实现其简单的添加节点功能
双向链表 循环链表 静态链表 栈(Stack) 队列(Queue) 双端队列(Deque) 循环队列 哈希表(HashTable) 树形数据结构 二叉树(BinaryTree)、二叉搜索树(BinarySearchTree、BST) 平衡二叉搜索树...
1.在一个双向链表中,删除任意一个结点 2.已知两个有序链表,实现将这两个链表的结合并且还是有序的 3.检查一个单链表中是否有环 4.已知链表的头结点head,写一个函数把这个链表逆序 约瑟夫环 5.循环链表--输入M,N...
数据结构与算法 —— Java 实现(链表)一、单链表1.1 链表的定义1.2 链表添加一个新的节点1.3 判断当前节点是否为最后一个节点 (isLast)1.4 删除下一节点 (removeNext)1.5 显示节点信息(show)1.6 插入一个...
使用纯Java语言写出来的数据结构,包含数据结构有 单向链表,双向链表,单向循环链表,双向循环链表,二叉树,队列,栈等, 关于实现的种类有分多种类型,包含有链表或者数组,二叉树里面包含有常见的二叉查找树,...
Java 数据结构目录 整理一下。。。 【动态扩容数组】动态扩容数组 ArrayList实现源码(Java、C++) 【链表List】单向链表 SingleLinkedList、双向链表 LinkedList 实现源码 【循环链表CircleList】单向循环链表、...
4.8 双向链表 第5章 树 5.1 引论 5.2 二叉树 5.3 遍历二叉树 5.4 其它二叉树操作 5.5 线索二叉树 5.6 堆 5.7 二叉查找树 5.8 选拔树 5.9 森林 5.10 不相交集合的表示 5.11 二叉树的计数 5.12 参考文献...
全国计算机二级JAVA笔试分类模拟题算法和数据结构、程序设计基础全文共21页,当前为第1页。全国计算机二级JAVA笔试分类模拟题算法和数据结构、程序设计基础全文共21页,当前为第1页。二级JAVA笔试分类模拟题算法和...
【1】结构定义与测试部分 1.顺序表 2.单链表 3.循环链表 4.双向链表 5.结点定义 【2】案例实践 1.一元多项式 2.约瑟夫环
1.1 数据结构的基本概念 1.2 抽象数据类型 1.3 算法和算法的时间复杂度 1.4 算法的空间复杂度分析 1.5 Java语言的工具包 2.1 线性表 2.2 顺序表 2.3 单链表 2.4 循环单链表 2.5 双向链表 2.6 仿真链表 2.7 面向对象...
根据指针的指向,链表能形成不同的结构,例如单链表,双向链表, 循环链表等。 链表的优点: 1. 链表是很常⽤的⼀种数据结构,不需要初始化容量,可以任意加减元素; 2. 添加或者删除元素时只需要改变前后两个元素...
数据结构与算法 排序算法 内排序 八大基础排序 选择排序 简单选择排序 思想 每次选择最大的数插入到末尾中 做法 外层for循环控制次数 内层for循环找出最大的值的角...
判断青蛙过河leetcode ...《Java数据结构和算法.(中文第二版)》 《算法导论中文版》 《剑指Offer》 练习题 经典算法大全 leetcode 学习进度 ####递归 递归 cn.diyai.recursion.Recursion 斐波那契数列 跳台阶 ...