欢迎您请 /
Java实现单向链表和双向链表
来源：本站 |
Java实现单向链表和双向链表：单向链表的特点是链表的链接方向是单向的，对链表的访问要通过顺序读取从头部开始；链表是使用指针进行构造的列表。又称为结点列表，因为链表是由一个个结点组装起来的；其中每个结点都有指针成员变量指向列表中的下一个结点。
public class Node {
public Node(String value){
this.value =
public class LinkedListTest {
public void add(Node node){
if(first == null){
last.next =
public Node getFirstNode(){
public Node getLastNode(){
public int getSize(){
int size = 0;
Node node =
while(node != null){
node = node.
public static void main(String[] args) {
LinkedListTest link = new LinkedListTest();
Node node1 = new Node(&node1&);
Node node2 = new Node(&node2&);
Node node3 = new Node(&node3&);
link.add(node1);
link.add(node2);
link.add(node3);
System.out.println(link.getSize());
System.out.println(link.getFirstNode().value);
System.out.println(link.getLastNode().value);
2、双向链表
双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。
public class DoublyNode {
public DoublyNode(String value){
this.value =
public class DoublyLinkedListTest {
public void add(DoublyNode node){
if(first == null){
last.next =
node.pre =
last.next =
first.pre =
【版权与免责声明】如发现内容存在版权问题，烦请提供相关信息发邮件至，我们将及时沟通与处理。本站内容除非来源注明方便了，否则均为网友转载，涉及言论、版权与本站无关。
本文永久链接：/news/show-57955.html
微信扫一扫，关注方便了
官网二维码扫描关注方便了链表-java实现双向链表 -
- ITeye技术网站
博客分类：
前面已经总结了单向链表，有兴趣的兄弟可以进我博客看一下。。。大家对比就可以看出，实现同样的功能单向链表要比双向链表痛苦的多。所以呀不断地总结前辈留下的东西，是社会进步的基础呀。可以直接看LinkedList的源码，其就是个双向链表。
一、双向链表的结构。
(1)、首先节点的结构，其中包含本节点内容，同时需要知道前面是谁后面是谁。
private static class Entry&E& {
//后一个节点
Entry&E& nextE
//前一个节点
Entry&E& previousE
public Entry(E e, Entry&E& previousEntry, Entry&E& nextEntry) {
this.nextEntry = nextE
this.previousEntry = previousE
其中e则指向本节点的元素，而nextEntry则指向下一个节点，previousEntry则指向前一个节点。
(2)、需要定义一个节点，其同时知道表头，同时知道表尾，这里就暂时定义为head。
private transient Entry&E& head = new Entry&E&(null, null, null);
public DoubleChain() {
head.nextEntry = head.previousEntry =
可以看出，在初始化方法中，直接将表头和表尾直接都指向head。这样在head的基础上不管怎么增加元素都逃脱不了与head关系。牢记head.nextEntry表头，head.previousEntry表尾。
(3)、同样记录节点的个数只是为了提高效率，不是必要。
public int size() {
return this.
好了有这三样，就足够了。就看我们如何用他们了。
二、内部实现。
(1)、方法addBefore。由于一开始就初始化了head，有了head作为基准，玩转整个链表也就靠这个方法了。
private void addBefore(E e, Entry&E& entry) {
//新节点的初始化，指定新节点的前一个节点和后一个节点
Entry&E& newEntry = new Entry&E&(e, entry.previousEntry, entry);
//告知新节点的前一个节点其后面是新节点
newEntry.previousEntry.nextEntry = newE
//告知新节点的后一个节点其前节点是新节点
newEntry.nextEntry.previousEntry = newE
可以看出，通过指定的元素创建一个新的节点。然后将其前前后后的关系都打通就好了。
(2)、表头插入。再简单不过了，直接在head.nextEntry前增加就好了，直接调用addBefore。效率高
public void addHead(E e) {
this.addBefore(e, head.nextEntry);
(3)、尾插入。同样简单，直接在head.previous前增加就好了，同样调用addBefore。效率高
public void add(E e) {
this.addBefore(e, head);
(4)、指定节点插入（插队）。同样需要插队，但是由于其节点的双向性，则不需要进行特殊处理，直接循环找出指定的节点元素就好了。效率低
public void addSpecifyIndex(E e, int index) {
int count = 0;
for (Entry&E& p = head.nextE p != p = p.nextEntry) {
if (count == index) {
this.addBefore(e, p);
(5)、指定节点获取元素。同样循环找出。效率低
public E get(int index) {
int count = 0;
E result =
for (Entry&E& p = head.nextE p != p = p.nextEntry) {
if (count == index) {
result = p.e;
(6)、指定节点删除。同理，找到要删除的节点，让指定节点的前后直接相通就OK了。效率低
public void remove(int index) {
int count = 0;
for (Entry&E& p = head.nextE p != p = p.nextEntry) {
if (count == index) {
p.previousEntry.nextEntry= p.nextE
p.nextEntry.previousEntry=p.previousE
(7)、循环。为了好进行遍历演示，下面的就是循环遍历所用的了，大家随意看一下就好了。
private Entry&E&
public boolean hasNext() {
return current !=
public E next() {
E result = current.e;
current = current.nextE
public void setCursor(int index) {
int count = 0;
for (Entry&E& p = head.nextE p != p = p.nextEntry) {
if (count == index) {
三、测试。。一个main方法，测试一下。
public static void main(String[] args) {
DoubleChain&String& doubleChain = new DoubleChain&String&();
for (int i = 0; i & 4; i++) {
doubleChain.add(i + "");
doubleChain.addHead("head");
doubleChain.add("tail");
// 指定节点插入
doubleChain.addSpecifyIndex("Specify", 1);
// 指定节点删除
doubleChain.remove(3);
// 设置循环的初始节点
doubleChain.setCursor(0);
int count = 0;
System.out.println("######SIZE" + doubleChain.size() + "#######");
while (doubleChain.hasNext()) {
System.out.println("index:" + count + ",entry:"
+ doubleChain.next());
System.out.println(doubleChain.get(doubleChain.size() - 2));
四、总结。。
可以看出，从结构上讲，双向链表和单项链表最大的区别在于每个节点都是双向的。从效率上讲，提高了尾插入的效率，但是对于插队同样效率不高。如果需要反复进行插队操作的同学注意了，LinkedList的效率会很低的哦。
五、全部代码。。
package paladin.
public class DoubleChain&E& implements Chain&E& {
private transient Entry&E& head = new Entry&E&(null, null, null);
private Entry&E&
public DoubleChain() {
head.nextEntry = head.previousEntry =
private void addBefore(E e, Entry&E& entry) {
//新节点的初始化，指定新节点的前一个节点和后一个节点
Entry&E& newEntry = new Entry&E&(e, entry.previousEntry, entry);
//告知新节点的前一个节点其后面是新节点
newEntry.previousEntry.nextEntry = newE
//告知新节点的后一个节点其前节点是新节点
newEntry.nextEntry.previousEntry = newE
public void add(E e) {
this.addBefore(e, head);
public void addHead(E e) {
this.addBefore(e, head.nextEntry);
public void addSpecifyIndex(E e, int index) {
int count = 0;
for (Entry&E& p = head.nextE p != p = p.nextEntry) {
if (count == index) {
this.addBefore(e, p);
public void remove(int index) {
int count = 0;
for (Entry&E& p = head.nextE p != p = p.nextEntry) {
if (count == index) {
p.previousEntry.nextEntry= p.nextE
p.nextEntry.previousEntry=p.previousE
public E get(int index) {
int count = 0;
E result =
for (Entry&E& p = head.nextE p != p = p.nextEntry) {
if (count == index) {
result = p.e;
public boolean hasNext() {
return current !=
public E next() {
E result = current.e;
current = current.nextE
public void setCursor(int index) {
int count = 0;
for (Entry&E& p = head.nextE p != p = p.nextEntry) {
if (count == index) {
public int size() {
return this.
private static class Entry&E& {
//后一个节点
Entry&E& nextE
//前一个节点
Entry&E& previousE
public Entry(E e, Entry&E& previousEntry, Entry&E& nextEntry) {
this.nextEntry = nextE
this.previousEntry = previousE
public static void main(String[] args) {
DoubleChain&String& doubleChain = new DoubleChain&String&();
for (int i = 0; i & 4; i++) {
doubleChain.add(i + "");
doubleChain.addHead("head");
doubleChain.add("tail");
// 指定节点插入
doubleChain.addSpecifyIndex("Specify", 1);
// 指定节点删除
doubleChain.remove(3);
// 设置循环的初始节点
doubleChain.setCursor(0);
int count = 0;
System.out.println("######SIZE" + doubleChain.size() + "#######");
while (doubleChain.hasNext()) {
System.out.println("index:" + count + ",entry:"
+ doubleChain.next());
System.out.println(doubleChain.get(doubleChain.size() - 2));
mountain_king
浏览: 10504 次
来自: 成都
获取图片明暗度可以通过获取HSB值来判断吧
取出杂线的效果不是很理想呀，
楼主，怎么判断图片的明暗度呢？
一般情况下，二值化主要针对文字、表格相应的图片。很少存在二值化 ...
使用静态内部类，主要是考虑到Entry不需要引用外部的资源，并 ...剔除链表中重复的结点JAVA - 综合当前位置:& &&&剔除链表中重复的结点JAVA剔除链表中重复的结点JAVA&&网友分享于：&&浏览：0次删除链表中重复的结点JAVA思路：定义四个结点，前结点prenode,当前结点node,下一个结点nextnode，删除结点delnode,在遇到删除结点时候要保证prenode连接上nextnode,防止断裂情况。
public static void deleteDuplication(ListNote root){
if(root==null){
ListNote preNode=null;
ListNote node=
while(node!=null){
ListNote nextNode=node.getNext();
boolean needDelete=false;
if(nextNode!=null&&nextNode.getValue()==node.getValue())
needDelete=true;
if(!needDelete){
node=node.getNext();
int value=node.getValue();
ListNote toBeDel=
while(toBeDel!=null&&toBeDel.getValue()==value){
nextNode=toBeDel.getNext();
toBeDel=nextN
if(preNode==null){
root=nextN
preNode.setNext(nextNode);
node=nextN
定义单向链表ListNote
public class ListNote {
ListNote NextN
private int value;
public ListNote(){
public ListNote(int value){
this.value=value;
ListNote getNext(){
return NextN
public void setNext(ListNote next){
this.NextNote=
public int getValue(){
return value;
public void setValue(int value){
this.value=value;
12345678910
12345678910
12345678910 上一篇：下一篇：文章评论相关解决方案 1234567891011 Copyright & &&版权所有