以前确实没有仔细看过链表，只知道节点中包含前后节点引用，直到有一天被人问到了，才明白自己对其理解甚少，花了点时间总结了一下，现在把结果拿出来和大家一起分享，希望得到指正。后续会有双向链表分享。
一、单向链表的结构。
(1)、首先节点的结构，其中包含本节点内容，以及需要指向下一个节点。
private static class Entry<E>{
E e;
Entry<E> nextEntry;
public Entry(E e,Entry<E> nextEntry){
this.e=e;
this.nextEntry=nextEntry;
}
}
其中e则指向本节点的对象，而nextEntry则指向下一个节点。
(2)、任何时候都需要知道表头在哪里。毕竟是单向链表嘛，因为只有一个方向，找到了表头就能找到全部。
private Entry<E> head;
(3)、还可以记录链表中总共有多少个节点。它是在某些判断时为了提高效率而存在的。不是绝对需要的。毕竟知道表头后，一个一个按顺序去寻找就好了。
private int size;
public int size(){
return this.size;
}
好了有这三样，就足够了。就看我们如何用他们了。
二、内部实现。
(1)、第一次向链表中插入。此时链表中节点为null，第一次插入，无非就是把节点头插入而已。
可以看出就是把链表头初始化了，并且链表大小涨1。其中modCount记录整个链表修改的次数，链表的增加和删除它都会增加。毕竟第一次插入相对外调用是透明的，所以应该是私有的咯。（透明就是不可见，这里只得是外部没必要知道它的存在）
private void addFirst(E e){
head=new Entry<E>(e,null);
size++;
modCount++;
}
(2)、表头插入。在链表的头前插入一个元素，新增的元素变成新的表头。这个插入是效率最高的，毕竟你时刻知道链表的头在哪里。
public void addHead(E e){
if(head==null){
this.addFirst(e);
}else{
Entry<E> newEntry=new Entry<E>(e,head);
head=newEntry;
size++;
modCount++;
}
}
可以看出头为null的时候，则表明链表中没值，只需调用第一次插入。否则对给定的元素创新增一个节点，新增节点的下一个指向头节点，当然此时自己已经变成头结点了，索引要更新头节点的引用。（可以看出想要清空链表，只需要将头置为null就好了）
(3)、指定节点插入（插队）。在链表的指定节点插入一个元素，效率非常低。由于规则上你只能从队伍第一个开始往后找，找到你要插队位置的前一个，并将你插入其中，你先要告诉你身前人你在他身后，并且你自己要清楚你身后是谁。反正够麻烦的。
public void addSpecifyIndex(E e,int index){
if(index<0||index>size||size==0){
throw new NoSuchElementException();
}
if(index==0){
this.addHead(e);
return;
}
int count=0;
for (Entry<E> p=head; p!=null;p=p.nextEntry) {
if(count+1==index){
Entry<E> newEntry=new Entry<E>(e,p.nextEntry);
p.nextEntry=newEntry;
size++;
modCount++;
return;
}
count++;
}
}
先进行判断index是否正确，规定不能插入null链表。而且不能跳着走，毕竟链表要连起来。由于要找到前一个，但是表头的前一个是没有的，所以index==0时要单独判断。后面则用count进行计数，找到其index-1节点，然后进行插队处理。
(4)、尾插入。其实也是插队了，只是总是需要插到最后一个之后。
public void add(E e){
if(head==null){
this.addFirst(e);
}else{
this.addSpecifyIndex(e, size);
}
}
(5)、指定节点获取元素。效率低，同样从头开始找到指定的节点把其中元素取出
public E get(int index){
if(index<0||index>=size){
throw new NoSuchElementException();
}
E result=null;
int count=0;
for (Entry<E> p=head;p!=null;p=p.nextEntry) {
if(count==index){
result=p.e;
}
count++;
}
return result;
}
(6)、指定节点删除。效率低，同样需要找到指定节点前一节点，直接把指定节点跳过就好了。
public void remove(int index){
if(index<0||index>=size){
throw new NoSuchElementException();
}
if(index==0){
head=head.nextEntry;
size--;
modCount++;
return;
}
int count=0;
for (Entry<E> p=head;p.nextEntry!=null;p=p.nextEntry) {
if(count+1==index){
p.nextEntry=p.nextEntry.nextEntry;
size--;
modCount++;
break;
}
count++;
}
}
(7)、循环。为了好进行遍历演示，下面的就是循环遍历所用的了，大家随意看一下就好了。
private transient Entry<E> current;
public void setCursor(int index){
if(index<0||index>=size){
throw new NoSuchElementException();
}
int count=0;
for (Entry<E> p=head;p!=null;p=p.nextEntry) {
if(count==index){
current=p;
break;
}
count++;
}
}
public boolean hasNext(){
return current!=null;
}
public E next(){
E result=current.e;
current=current.nextEntry;
return result;
}
三、测试。。一个main方法，测试一下。
public static void main(String[] args) {
SingleChain<String> singleChain=new SingleChain<String>();
for (int i = 0; i < 4; i++) {
singleChain.add(i+"");
}
//头插入
// singleChain.addHead("head");
//尾插入
// singleChain.add("tail");
//指定节点插入
// singleChain.addSpecifyIndex("Specify", 1);
//指定节点删除
// singleChain.remove(3);
//设置循环的初始节点
singleChain.setCursor(0);
int count=0;
System.out.println("######SIZE"+singleChain.size()+"#######");
while(singleChain.hasNext()){
System.out.println("index:"+count+",entry:"+singleChain.next());
count++;
}
System.out.println(singleChain.get(singleChain.size()-1));
}
四、全部代码
package paladin.chain;
import java.util.NoSuchElementException;
public class SingleChain<E> implements Chain<E>{
private Entry<E> head;
private transient Entry<E> current;
private int size;
private int modCount;
private void addFirst(E e){
head=new Entry<E>(e,null);
size++;
modCount++;
}
public void addHead(E e){
if(head==null){
this.addFirst(e);
}else{
Entry<E> newEntry=new Entry<E>(e,head);
head=newEntry;
size++;
modCount++;
}
}
public void addSpecifyIndex(E e,int index){
if(index<0||index>size||size==0){
throw new NoSuchElementException();
}
if(index==0){
this.addHead(e);
return;
}
int count=0;
for (Entry<E> p=head; p!=null;p=p.nextEntry) {
if(count+1==index){
Entry<E> newEntry=new Entry<E>(e,p.nextEntry);
p.nextEntry=newEntry;
size++;
modCount++;
return;
}
count++;
}
}
public void add(E e){
if(head==null){
this.addFirst(e);
}else{
this.addSpecifyIndex(e, size);
}
}
public E get(int index){
if(index<0||index>=size){
throw new NoSuchElementException();
}
E result=null;
int count=0;
for (Entry<E> p=head;p!=null;p=p.nextEntry) {
if(count==index){
result=p.e;
}
count++;
}
return result;
}
public void remove(int index){
if(index<0||index>=size){
throw new NoSuchElementException();
}
if(index==0){
head=head.nextEntry;
size--;
modCount++;
return;
}
int count=0;
for (Entry<E> p=head;p.nextEntry!=null;p=p.nextEntry) {
if(count+1==index){
p.nextEntry=p.nextEntry.nextEntry;
size--;
modCount++;
break;
}
count++;
}
}
public void setCursor(int index){
if(index<0||index>=size){
throw new NoSuchElementException();
}
int count=0;
for (Entry<E> p=head;p!=null;p=p.nextEntry) {
if(count==index){
current=p;
break;
}
count++;
}
}
public boolean hasNext(){
return current!=null;
}
public E next(){
E result=current.e;
current=current.nextEntry;
return result;
}
public int size(){
return this.size;
}
public static void main(String[] args) {
SingleChain<String> singleChain=new SingleChain<String>();
for (int i = 0; i < 4; i++) {
singleChain.add(i+"");
}
//头插入
// singleChain.addHead("head");
//尾插入
// singleChain.add("tail");
//指定节点插入
// singleChain.addSpecifyIndex("Specify", 1);
//指定节点删除
// singleChain.remove(3);
//设置循环的初始节点
singleChain.setCursor(0);
int count=0;
System.out.println("######SIZE"+singleChain.size()+"#######");
while(singleChain.hasNext()){
System.out.println("index:"+count+",entry:"+singleChain.next());
count++;
}
System.out.println(singleChain.get(singleChain.size()-1));
}
private static class Entry<E>{
E e;
Entry<E> nextEntry;
public Entry(E e,Entry<E> nextEntry){
this.e=e;
this.nextEntry=nextEntry;
}
}
}
分享到：
相关推荐
Java SE程序 类实现单向链表Java SE程序 类实现单向链表Java SE程序 类实现单向链表Java SE程序 类实现单向链表Java SE程序 类实现单向链表Java SE程序 类实现单向链表Java SE程序 类实现单向链表Java SE程序 类实现...
附件是逆序输出单向链表_Java 版本源码，代码首先定义了一个Node类来表示链表的节点，然后定义了一个LinkedList类来表示单链表，并提供了添加节点、打印链表和逆序链表的方法。最后，在Main类中创建了一个链表实例，...
总结来说，这个压缩包提供的源代码为我们展示了如何在Java中实现单向循环链表的数据结构，并通过`List`接口提供了丰富的操作方法。通过学习和理解这些代码，开发者可以深入理解链表的工作原理，并能熟练运用到实际...
### 链表构造知识点详解 #### 一、链表基本概念 链表是一种常见的线性...以上是关于单向链表构造的基本知识点及其对应的Java实现代码。这些方法提供了对链表的基本操作能力，可以在此基础上进行更复杂的功能开发。
附件是Java 实现的去除链表重复元素。在Java中，去除单链表中的重复元素可以通过使用哈希集合（HashSet）来实现，该集合用于存储已经遍历过的元素。在遍历链表的过程中，我们将每个元素与集合中的元素进行比较，如果...
这是一个单向链表，它具有插入与删除节点的功能。Entry类实现了链表的各节点。
本话题主要探讨两种常用的数据结构——单链表和双向链表在Java中的实现，以及相关的操作，如在头部添加节点、在尾部添加节点、遍历、逆置和删除。 首先，我们来理解单链表和双向链表的基本概念。单链表是一种线性...
Java实现单向链表反转 Java实现单向链表反转是指将单向链表的顺序颠倒，例如原链表为A->B->C->D->E->F，反转后变为F->E->D->C->B->A。这种操作在实际开发中非常有用，例如在数据处理、数据分析等领域。 单向链表...
在Java中，单向链表可以被实现为LinkedList类，与ArrayList相比，它提供了不同的操作性能特点。ArrayList是基于数组实现的，而LinkedList则是通过节点之间的链接来存储数据，这使得在链表中插入和删除元素更加高效，...
数据结构-链表 JAVA语言实现,包含单向链表、双向链表、循环链表的遍历、删除和插入 详细介绍：http://blog.csdn.net/z740852294/article/details/77369439
在Java中实现循环链表，我们需要定义一个节点类（Node）来存储数据和指向下一个节点的引用，同时在链表类（CircularLinkedList）中维护头节点和当前大小。以下是实现的关键点： 1. **节点类(Node)**：创建一个内部...
双向链表相比单向链表的优点在于其灵活性，但也有额外的存储开销，因为每个节点都需要存储两个指针。在某些需要频繁进行插入和删除操作的场景下，如实现高效的栈或队列，双向链表是理想的选择。 在实际开发中，Java...
附件是.java 文件，实现了单链表的逆序算法，文件绿色安全，仅供学习交流使用，欢迎大家下载学习交流！ 首先定义了一个ListNode类来表示链表中的节点，然后在reverseList方法中实现了链表的逆序。reverseList方法...
类似约瑟夫环问题。有一群人组成一个圈。从头开始按照顺时针方向从1开始依次报数。报到到9的人就离开圈子。其左手边的人接着从1开始报数。依此进行，直到剩最后一个人为止。
在Java中，链表主要分为两种类型：单向链表和双向链表。单向链表的每个节点只能指向下一个节点，而双向链表的节点则可以同时指向前后两个节点，提供了更灵活的遍历方式。 1. 单向链表： - 单向链表的节点定义：...
java语言模拟单向链表,JAVA数据结构
### JAVA单向链表的实现知识点详解 #### 一、链表基础概念 在深入了解Java单向链表的具体实现之前，我们首先需要了解链表的基本概念。链表是一种线性数据结构，它由一系列节点组成，每个节点包含两部分：数据域和...