锐客网

  1. 首页 > 睿知 > it技术 > >

java链表代码实现 java链表怎么实现

IT技术节点

在Java中如何实现双向链表?双向链表：就是有双向指针，即双向的链域 。\x0d\x0a链结点的结构：\x0d\x0a┌────┬────┬────────┐\x0d\x0a│ data │next │previous│\x0d\x0a└────┴────┴────────┘\x0d\x0a双向链表不必是双端链表(持有对最后一个链结点的引用)，双端链表插入时是双向的 。\x0d\x0a有两条链：一条从头到尾，一条从尾到头，删除遍历时也是双向的 。\x0d\x0a/**\x0d\x0a * 双向链表\x0d\x0a */\x0d\x0apublic class DoublyLinkedList {\x0d\x0aprivate Link head;//首结点\x0d\x0aprivate Link rear;//尾部指针\x0d\x0apublic DoublyLinkedList() {}\x0d\x0apublic T peekHead() {\x0d\x0aif (head != null) {\x0d\x0areturn head.data;\x0d\x0a}\x0d\x0areturn null;\x0d\x0a}\x0d\x0apublic boolean isEmpty() {\x0d\x0areturn head == null;\x0d\x0a}\x0d\x0apublic void insertFirst(T data) {// 插入 到 链头\x0d\x0aLink newLink = new Link(data);\x0d\x0aif (isEmpty()) {//为空时 ， 第1次插入的新结点为尾结点\x0d\x0arear = newLink;\x0d\x0a} else {\x0d\x0ahead.previous = newLink; //旧头结点的上结点等于新结点\x0d\x0a}\x0d\x0anewLink.next = head; //新结点的下结点旧头结点\x0d\x0ahead = newLink; //赋值后，头结点的下结点是旧头结点 ， 上结点null\x0d\x0a}\x0d\x0apublic void insertLast(T data) {//在链尾 插入\x0d\x0aLink newLink = new Link(data);\x0d\x0aif (isEmpty()) {\x0d\x0ahead = newLink;\x0d\x0a} else {\x0d\x0arear.next = newLink;\x0d\x0a}\x0d\x0anewLink.previous = rear;\x0d\x0arear = newLink; //赋值后，尾结点的上结点是旧尾结点，下结点null\x0d\x0a}\x0d\x0apublic TdeleteHead() {//删除 链头\x0d\x0aif (isEmpty()) return null;\x0d\x0aLink temp = head;\x0d\x0ahead = head.next; //变更首结点，为下一结点\x0d\x0aif (head != null) {\x0d\x0ahead.previous = null;\x0d\x0a} else {\x0d\x0arear = null;\x0d\x0a}\x0d\x0areturn temp.data;\x0d\x0a}\x0d\x0apublic TdeleteRear() {//删除 链尾\x0d\x0aif (isEmpty()) return null;\x0d\x0aLink temp = rear;\x0d\x0arear = rear.previous; //变更尾结点 ， 为上一结点\x0d\x0aif (rear != null) {\x0d\x0arear.next = null;\x0d\x0a} else {\x0d\x0ahead = null;\x0d\x0a}\x0d\x0areturn temp.data;\x0d\x0a}\x0d\x0apublic T find(T t) {//从头到尾find\x0d\x0aif (isEmpty()) {\x0d\x0areturn null;\x0d\x0a}\x0d\x0aLink find = head;\x0d\x0awhile (find != null) {\x0d\x0aif (!find.data.equals(t)) {\x0d\x0afind = find.next;\x0d\x0a} else {\x0d\x0abreak;\x0d\x0a}\x0d\x0a}\x0d\x0aif (find == null) {\x0d\x0areturn null;\x0d\x0a}\x0d\x0areturn find.data;\x0d\x0a}\x0d\x0apublic T delete(T t) {\x0d\x0aif (isEmpty()) {\x0d\x0areturn null;\x0d\x0a}\x0d\x0aLink current = head;\x0d\x0awhile (!current.data.equals(t)) {\x0d\x0acurrent = current.next;\x0d\x0aif (current == null) {\x0d\x0areturn null;\x0d\x0a}\x0d\x0a}\x0d\x0aif (current == head) {\x0d\x0ahead = head.next;\x0d\x0aif (head != null) {\x0d\x0ahead.previous = null;\x0d\x0a}\x0d\x0a} else if (current == rear) {\x0d\x0arear = rear.previous;\x0d\x0aif (rear != null) {\x0d\x0arear.next = null;\x0d\x0a}\x0d\x0a} else {\x0d\x0a//中间的非两端的结点，要移除current\x0d\x0acurrent.next.previous = current.previous;\x0d\x0acurrent.previous.next = current.next;\x0d\x0a}\x0d\x0areturn current.data;\x0d\x0a}\x0d\x0apublic boolean insertAfter(T key, T data) {//插入在key之后, key不存在return false\x0d\x0aif (isEmpty()) {\x0d\x0areturn false;\x0d\x0a}\x0d\x0aLink current = head;\x0d\x0awhile (!current.data.equals(key)) {\x0d\x0acurrent = current.next;\x0d\x0aif (current == null) {\x0d\x0areturn false;\x0d\x0a}\x0d\x0a}\x0d\x0aLink newLink = new Link(data);\x0d\x0aif (current == rear) {\x0d\x0arear = newLink;\x0d\x0a} else {\x0d\x0anewLink.next = current.next;\x0d\x0acurrent.next.previous = newLink;\x0d\x0a}\x0d\x0acurrent.next = newLink;\x0d\x0anewLink.previous = current;\x0d\x0areturn true;\x0d\x0a}\x0d\x0apublic void displayList4Head() {//从头开始遍历\x0d\x0aSystem.out.println("List (first--last):");\x0d\x0aLink current = head;\x0d\x0awhile (current != null) {\x0d\x0acurrent.displayLink();\x0d\x0acurrent = current.next;\x0d\x0a}\x0d\x0a}\x0d\x0apublic void displayList4Rear() {//从尾开始遍历\x0d\x0aSystem.out.println("List (last--first):");\x0d\x0aLink current = rear;\x0d\x0awhile (current != null) {\x0d\x0acurrent.displayLink();\x0d\x0acurrent = current.previous;\x0d\x0a}\x0d\x0a}\x0d\x0a\x0d\x0aclass Link {//链结点\x0d\x0aT data;//数据域\x0d\x0aLink next; //后继指针 ， 结点链域\x0d\x0aLink previous; //前驱指针 ， 结点链域\x0d\x0aLink(T data) {\x0d\x0athis.data = https://www.04ip.com/post/data;/x0d/x0a}/x0d/x0avoid displayLink() {/x0d/x0aSystem.out.println("the data is " + data.toString());\x0d\x0a}\x0d\x0a}\x0d\x0apublic static void main(String[] args) {\x0d\x0aDoublyLinkedList list = new DoublyLinkedList();\x0d\x0alist.insertLast(1);\x0d\x0alist.insertFirst(2);\x0d\x0alist.insertLast(3);\x0d\x0alist.insertFirst(4);\x0d\x0alist.insertLast(5);\x0d\x0alist.displayList4Head();\x0d\x0aInteger deleteHead = list.deleteHead();\x0d\x0aSystem.out.println("deleteHead:" + deleteHead);\x0d\x0alist.displayList4Head();\x0d\x0aInteger deleteRear = list.deleteRear();\x0d\x0aSystem.out.println("deleteRear:" + deleteRear);\x0d\x0alist.displayList4Rear();\x0d\x0aSystem.out.println("find:" + list.find(6));\x0d\x0aSystem.out.println("find:" + list.find(3));\x0d\x0aSystem.out.println("delete find:" + list.delete(6));\x0d\x0aSystem.out.println("delete find:" + list.delete(1));\x0d\x0alist.displayList4Head();\x0d\x0aSystem.out.println("----在指定key后插入----");\x0d\x0alist.insertAfter(2, 8);\x0d\x0alist.insertAfter(2, 9);\x0d\x0alist.insertAfter(9, 10);\x0d\x0alist.displayList4Head();\x0d\x0a}\x0d\x0a}
用Java语言实现单向链表1.先定义一个节点类

推荐阅读


上一篇：包含jquerycheckboxselect的词条

下一篇：cad.net打开文件的简单介绍