数据结构之链表
本文共 4897 字，大约阅读时间需要 16 分钟。
数组的两大缺点：
1。若改变数组的大小就要创建一个新的数组，并需要从原数组复制所有的数据到新的数组
2。数组元素在内存中依次顺序存储，这意味着向数组插入一项要移动数组中的其他元素
因此，我们使用链式结构，链式结构是存储数据的结点以及指向其他节点的指针的集合。如此一来，节点可以位于内存的任意位置，而且从一个节点到另一个节点的传递可以通过在结构中存储节点间引用来实现。
一。单向链表
1。链表：
如果一个节点包含指向另一个节点的数据值，那么多个节点可以连接成一串，只通过一个变量访问整个节点序列，这样的节点序列称为链表（linked list）
2。单向链表：
如果每个节点仅包含其指向后继节点的引用，这样的链表称为单向链表。
一个整型单向链表的实现：
package com.sohu.blog.denns_zane.list;
/** */ /** 
* @author dennis * @Description 整型单向链表节点
*/ public class IntSLLNode 
{ public int info; // 用户信息 public IntSLLNode next; // 下一个节点，自引用 
/** */ /** * @param info * @param next
*/ public IntSLLNode( int info, IntSLLNode next) { this .info = info; this .next = next; } /** */ /** * @param info */ public IntSLLNode( int info) { this (info, null ); } } /** */ /** * */ package com.sohu.blog.denns_zane.list; /** */ /** * @author dennis * desc: 整型单向链表 */ public class IntSLList { protected IntSLLNode head, tail; public IntSLList() { head = tail = null ; } public boolean isEmpty() { return head == null ; } /** */ /** * @description 增加新节点，并设置它的next为原head * @param el */ public void addToHead( int el) { head = new IntSLLNode(el, head); if (tail == null ) tail = head; } /** */ /** * @description 增加新节点，并设置原tail的next为新节点 * @param el */ public void addToTail( int el) { if ( ! isEmpty()) { tail.next = new IntSLLNode(el); tail = tail.next; } else { head = tail = new IntSLLNode(el); } } public int deleteFromHead() { if (head == null ) throw new NullPointerException(); int el = head.info; if (head == tail) head = tail = null ; else head = head.next; return el; } public int deleteFromTail() { if (head == null ) throw new NullPointerException(); int el = tail.info; if (head == tail) head = tail = null ; else { IntSLLNode temp; for (temp = head; temp.next != null && temp.next != tail; temp = temp.next) tail = temp; System.out.println(tail.info); tail.next = null ; } return el; } public void printAll() { for (IntSLLNode temp = head; temp != null ; temp = temp.next) System.out.print(temp.info + " " ); } public boolean isInList( int el) { for (IntSLLNode temp = head; temp != null ; temp = temp.next) { if (temp.info == el) return true ; } return false ; } /** */ /** * @param el */ public void delete( int el) { if ( ! isEmpty()) { if (head == tail && head.info == el) head = tail = null ; else if (head.info == el) head = head.next; else { IntSLLNode pred, temp; // pred为找的节点的前一节点，temp即为找到的节点 for (pred = head, temp = head.next; temp != null ; pred = pred.next, temp = temp.next) { if (temp.info == el) { pred.next = temp.next; // 前一节点的next设置为当前节点的next if (temp == tail) tail = pred; } } } } } } 二。双向链表
单向链表的deleteFromTail()方法指出了单向链表的固有问题，这种链表的节点仅仅包含指向后继节点的引用，所以无法立即访问它的前驱节点，不得不扫描整个链表来查找此前驱节点。因此，我们重新定义链表节点，包含两个引用，一个指向前驱节点，一个指向后驱节点，也就是——双向链表。 一个整型双向链表的实现： /** */ /** * */ package com.sohu.blog.denns_zane.list; /** */ /** * @author dennis desc:双向链表节点 */ public class IntDLLNode { public int info; public IntDLLNode prev, next; /** */ /** * @param info * @param prev * @param next */ public IntDLLNode( int info, IntDLLNode next, IntDLLNode prev) { super (); this .info = info; this .prev = prev; this .next = next; } public IntDLLNode( int info) { this (info, null , null ); } } /** */ /** * */ package com.sohu.blog.denns_zane.list; /** */ /** * @author dennis * */ public class IntDLList { private IntDLLNode head, tail; public IntDLList() { head = tail = null ; } public boolean isEmpty() { return head == null ; } public void addToHead( int el) { if (head == null ) head = new IntDLLNode(el); else { head = new IntDLLNode(el, head, null ); head.next.prev = head; } if (tail == null ) tail = head; } public void addToTail( int el) { if ( ! isEmpty()) { tail = new IntDLLNode(el, null , tail); tail.prev.next = tail; } else head = tail = new IntDLLNode(el); } public int removeFromTail() { if (head == null ) throw new NullPointerException(); int el = tail.info; if (head == tail) head = tail = null ; else { tail = tail.prev; tail.next = null ; } return el; } public int removeFromHead() { if (head == null ) throw new NullPointerException(); int el = head.info; if (head == tail) head = tail = null ; else { head = head.next; head.prev = null ; } return el; } public boolean isInList( int el) { if (head == null ) return false ; IntDLLNode temp; for (temp = head; temp != null ; temp = temp.next) { if (temp.info == el) { return true ; } } return false ; } public void delete( int el) { if (head == null ) throw new NullPointerException(); IntDLLNode temp; for (temp = head; temp != null ; temp = temp.next) { if (temp.info == el) { if (temp == head) { head.next.prev = null ; head = head.next; } else temp.prev.next = temp.next; } } } public void printAll() { IntDLLNode temp; for (temp = head; temp != null ; temp = temp.next) { System.out.print(temp.info + " " ); } System.out.println(); } } 文章转自庄周梦蝶 ，原文发布时间5.17
转载地址：http://occzl.baihongyu.com/
你可能感兴趣的文章
MEMCACHE常用的命令
查看>>
docker 基础
查看>>
Angular基础(七) HTTP & Routing
查看>>
使用Freeline提高你的工作效率
查看>>
FTP服务器
查看>>
爬百度新闻
查看>>
TCP协议与UDP协议的区别
查看>>
软件定时器算法
查看>>
VB.NET 自动打包程序
查看>>
CISCO引擎RPR SSO
查看>>
LINUX APACHE 安装测试
查看>>
Java导致登录UCS Manager异常
查看>>
HTTP协议
查看>>
Win10怎么改Host文件?Win10编辑host文件方法（无视权限）
查看>>
sql convert and cast
查看>>
我的NodeJS一年之旅总结
查看>>
MyBatis-3.4.2-源码分析6：解析XML之objectWrapperFactoryElement & reflectorFactoryElement
查看>>
javascript与获取鼠标位置有关的属性
查看>>
Oracle database 11.2.0.3.0 升级至 11.2.0.3.14
查看>>
heartbeat理论介绍
查看>>