万万没想到（实现单链表java的原理）java单链表数据结构，Java之单链表的实现，java单链表的实现，
刚刚用java实现链表，重新总结了一下，先把自己的理解写下来，以后一步步深入。
1.链表是一种物理存储单元上非连续、非顺序的存储结构。
2.链表是由那几个部分组成的呢？
由N个节点组成的，每一个节点就是一个对象：
每一个节点分为两部分：
1.数据域
2.指针域数据域用来存储数据，指针域用来链接各个链表。如图单链表
一、单向链表的结构。
(1)、首先节点的结构，其中包含本节点内容，以及需要指向下一个节点。
public class Node <E>{private Node<E> next;//指向下一个节点private E e;//数据域……………………}
其中e则指向本节点的对象，而next则指向下一个节点。
(2)、任何时候都需要知道表头在哪里。是单链表，因为只有一个方向，找到了表头就能找到全部。
// 声明头节点private Node<E> head;public MyLinkedList() {head = new Node<E>();// 实例化头节点…………………………}
(3)、记录链表的长度size。为了提高效率而存在的，一个一个往后去寻找就好了。
// 链表的大小private int size;/*** 获取单链表中存储的元素总数** @return 返回size属性*/public int size() {return size;}
有这三个part就可以来实现单链表的增删改查的功能啦~
二、内部实现。
(1)、增，即不断在链表后面加入节点。此时链表中仅有头节点，而第一次插入，此时头节点=尾节点，所以在此之前必须先实例化一个尾节点。
//声明 尾节点private Node<E> last;public MyLinkedList() {head = new Node<E>();// 实例化头节点last=head;//令头节点等于尾节点}
对给定的元素e实例化一个节点，令头节点（尾节点）指向元素e，同时令e为尾节点，即为在链表尾部加入新的节点
/*** 增* @param e要添加的元素*/public void add(E e) {Node<E> node = new Node<E>(e);// 以e实例化一个节点last.setNext(node);//往尾节点后加节点last=node;//该节点设为最后一个节点size++;}
(2)、删，指定节点删除。
1.效率低，需要找到指定节点前一节点，直接把指定节点跳过就好了。
2.若索引数=size-1，则令索引节点的前一个节点的指针域为空
/*** 删除指定的节点e,并返回e* @param i为索引号* @return 返回删除的元素e*/public E Delete(int index) {if (index < 0 || index > size)return null;if (index == 0) {// 当索引为1时，令头节点的下一个节点为头节点Node<E> node2 = head.getNext();head.setNext(node2.getNext());size--;return node2.getE();}// 获取要删除节点的前一个节点Node<E> bNode = Select(index - 1);// 获取要删除的节点Node<E> Node = bNode.getNext();// 获取要删除节点的后一个节点Node<E> nNode = Node.getNext();// 先建立删除节点的前一个节点和删除节点的后一个节点的关系bNode.setNext(nNode);// 清除dNode的下一个节点Node.setNext(null);size--;// 计数器减1return Node.getE();// 返回删除节点中的数据域}
(3)、改，实例化新节点，令它覆盖索引位置的节点
/*** 修改指点位置的数据域* @param x新内容* @param index索引位置* @return 返回修改后的数据*/public E Renew(E x, int index) {if (index < 0 || index > size || size == 0)return null;Node<E> xnode = new Node<E>(x);// 获取一个新节点Node<E> node = Select(index);node.setE(xnode.getE());return node.getE();}
(4)、查，指定节点获取元素。效率低，同样从头开始找到指定的节点把其中元素取出
/*** 获取指定索引位置的节点对象* @param index索引位置* @return 返回获取到的节点对象*/private Node<E> Select(int index) {Node<E> node = head.getNext();// 将头节点的下一个节点赋给nodefor (int i = 0; i < index; i++) {node = node.getNext();// 获取node的下一个节点}return node;}/*** 找到指定节点的数据域，并返回* @param index 索引* @return 节点的数据域*/public E GetE(int index) {if (index < 0 || index > size - 1)return null;Node<E> node = Select(index); // 查找指定索引位置的节点对象return node.getE();// 获取节点中的数据域元素并返回}
三.四个功能块就完成了，组成在一起就实现了链表，接下来看一下全部代码，节点类，链表类和链表测试类：
package yimi.Linkedlist;/*** 节点，链表由节点组成** @author 慧** @param <E>*/public class Node<E> {private Node<E> next;// 指向下一个节点private E e;// 数据域public Node() {}public Node(E e) {this.e = e;}public Node<E> getNext() {return next;}public void setNext(Node<E> next) {this.next = next;}public E getE() {return e;}public void setE(E e) {this.e = e;}}package yimi.Linkedlist;/*** 实现链表的功能，增删改查** @author 慧* @param <E>**/public class MyLinkedList<E> {// 声明头节点private Node<E> head;// 声明 尾节点private Node<E> last;// 链表的大小private int size;private int modcount;// 计算修改表的次数public MyLinkedList() {head = new Node<E>();// 实例化头节点last = head;}/*** 获取单链表中存储的元素总数** @return 返回size属性*/public int size() {return size;}/*** 获取指定索引位置的节点对象** @param index索引位置* @return 返回获取到的节点对象*/private Node<E> Select(int index) {Node<E> node = head.getNext();// 将头节点的下一个节点赋给nodefor (int i = 0; i < index; i++) {node = node.getNext();// 获取node的下一个节点}return node;}/*** 找到指定节点的数据域，并返回** @param index* 索引* @return 节点的数据域*/public E GetE(int index) {if (index < 0 || index > size - 1)return null;Node<E> node = Select(index); // 查找指定索引位置的节点对象return node.getE();// 获取节点中的数据域元素并返回}/*** 增** @param e要添加的元素*/public void add(E e) {Node<E> node = new Node<E>(e);// 以e实例化一个节点last.setNext(node);// 往尾节点后加节点last = node;// 该节点设为最后一个节点size++;}/*** 删除指定的节点e,并返回e** @param i为索引号* @return 返回删除的元素e*/public E Delete(int index) {if (index < 0 || index > size)return null;if (index == 0) {// 当索引为1时，令头节点的下一个节点为头节点Node<E> node2 = head.getNext();head.setNext(node2.getNext());size--;return node2.getE();}// 获取要删除节点的前一个节点Node<E> bNode = Select(index - 1);// 获取要删除的节点Node<E> Node = bNode.getNext();// 获取要删除节点的后一个节点Node<E> nNode = Node.getNext();// 先建立删除节点的前一个节点和删除节点的后一个节点的关系bNode.setNext(nNode);// 清除dNode的下一个节点Node.setNext(null);size--;// 计数器减1return Node.getE();// 返回删除节点中的数据域}/*** 修改指点位置的数据域* @param x新内容* @param index索引位置* @return 返回修改后的数据*/public E Renew(E x, int index) {if (index < 0 || index > size || size == 0)return null;Node<E> xnode = new Node<E>(x);// 获取一个新节点Node<E> node = Select(index);node.setE(xnode.getE());return node.getE();}}package yimi.Linkedlist;/*** 测试链表* @author 慧**/public class MyLinkedListTest {private static String x;/*** @param args*/public static void main(String[] args) {MyLinkedList<String> list=new MyLinkedList();list.add("one");list.add("two");list.add("three");list.add("four");for(int i=0;i<list.size();i++){System.out.println("输出第"+i+":"+list.GetE(i));}System.out.println();System.out.println("测试删除");x=list.Delete(0);System.out.println("删除了"+x);for(int i=0;i<=list.size();i++){System.out.println("输出第"+i+":"+list.GetE(i));}System.out.println("测试修改");list.Renew("Yimi", 2);for(int i=1;i<=list.size();i++){System.out.println("输出第"+i+":"+list.GetE(i));}System.out.println();System.out.println("测试查找");x=list.GetE(3);System.out.println("x="+x);}}
总结：
先看add方法，元素如何加入链表；
接着看取出GetE方法，注意index与0的关系，index不可以轻易等于0；
代码的洁简；
链表从0开始存储数据，且head不参与排序。
以上是单链表的理解和实现，有更深理解我会一直更新博客，以后可以实现双向链表，也会添上来~~
版权申明
本文系作者 @河马 原创发布在河马博客站点。未经许可，禁止转载。
暂无评论数据