【链表】
是一种线性表,但是并不会按线性的顺序存储数据,而是在每一个节点里存到下一个节点的指针(Pointer)。
由于不必须按顺序存储,链表在插入的时候可以达到O(1)的复杂度,比另一种线性表顺序表快得多,
但是查找一个节点或者访问特定编号的节点则需要O(n)的时间,
而顺序表相应的时间复杂度分别是O(㏒ n)和O(1)。
【单向链表】
是链表的一种,其特点是链表的链接方向是单向的,对链表的访问要通过顺序读取从头部开始
一个节点包含两个域,一个信息域和一个指针域,指针域指向下一个节点,最后一个节点指向一个空值
单向链表有一个头节点,可以不存储任何信息,包含一个指向第一个节点的指针
特点:
1.访问节点速度慢,需要从头节点一次遍历链表
2.更新节点快,节点不需要移动,更改相应指针即可
单向链表节点类定义如下:
public class Node<AnyType>{
AnyType element;
Node<AnyType> next;
}
要实现单向列表的相关操作,可定义类SingleLinkedList如下:
public class SingleLinkedList<AnyType>{
private static class Node<AnyType>{
AnyType element;
Node<AnyType> next;
public Node(AnyType element){
this.element = element;
}
}
private Node<AnyType> header = new Node<AnyType>(null);
private int size = 0;
public boolean isEmpty(){
return size==0;
}
public void makeEmpty(){
header = null;
}
public int size(){
return size;
}
/**
* Get element by index
* */
public AnyType get(int index){
return getNode(index).element;
}
/**
* Add the element to the end of this list
* */
public void add(AnyType element){
add(new Node<AnyType>(element));
}
/**
* Inserts the specified element at the specified position in this list
* 插入逻辑:
* 1.创建一个新节点
* 2.将原index节点的前一个节点的指针指向新节点
* 3.将新节点的指针指向index节点
* 4.插入后,新节点的位置为index
* */
public void add(int index,AnyType element){
Node<AnyType> newNode = new Node<AnyType>(element);
Node<AnyType> previous = getNode(index-1);
//index节点
Node<AnyType> node = previous.next;
//将原index节点的前一个节点的指针指向newNode
previous.next = newNode;
//将newNode的指针指向index节点
newNode.next = node;
size++;
}
/**
* Inserts the specified element at the specified position in this list
* 删除逻辑:
* 1.获得index节点的前一个节点previousNode
* 2.获得index节点的后一个节点nextNode
* 3.将previousNode的指针指向nextNode
* */
public void remove(int index){
Node<AnyType> previous = getNode(index-1);
Node<AnyType> next = previous.next.next;
previous.next = next;
size--;
}
/**
* 定义此方法是为了便于测试
* */
public List<Integer> getElements(){
if(isEmpty()){
return null;
}else{
List<Integer> elements = new ArrayList<Integer>();
Node<AnyType> node = (Node<AnyType>) header;
while(node.next!=null){
node = node.next;
elements.add(((Element)node.element).getValue());
}
return elements;
}
}
//private methods
private Node<AnyType> getNode(int index){
if(isEmpty()){
throw new RuntimeException("List is empty");
}
int i = 0;
Node<AnyType> node = header;
while(i<=index){
node = node.next;
i++;
}
return node;
}
private void add(Node<AnyType> newNode){
Node<AnyType> node = header;
while(node.next!=null){
node = node.next;
}
node.next = newNode;
size++;
}
}
如何实现链表反向:
/**
* 链表反向
* */
public void reverse(){
if(!isEmpty()){
reverse(header.next,header.next.next);
}
}
private void reverse(Node<AnyType> node,Node<AnyType> nextNode){
if(nextNode.next!=null){
reverse(nextNode,nextNode.next);
}else{
//如果该节点是表尾,那么用头节点指向此节点
header.next = nextNode;
}
//该节点的指针指向前一个节点P,并将节点P的指针设置为空
nextNode.next = node;
node.next = null;
}
分享到:
相关推荐
C#单向链表C#单向链表C#单向链表C#单向链表C#单向链表C#单向链表C#单向链表C#单向链表C#单向链表C#单向链表
1.随机产生或键盘输入一组元素,建立一个带头结点的单向链表(无序)。 2.遍历单向链表。 3.把单向链表中元素逆置(不允许申请新的结点空间)。 4.在单向链表中删除所有的偶数元素结点。 5.编写在非递减...
C#单向链表的实现的源码
单向链表架构代码,适合学习链表的学生学习!内附排序函数,打印函数,链表尾添项函数,删除函数。
04.单向链表以及单向链表的应用.ppt
这是一个单向链表,它具有插入与删除节点的功能。Entry类实现了链表的各节点。
将一个单向链表反向连接
C 语言版 单向链表 #include #include typedef struct student { int num; struct student *next; }st; st *creat() //创建链表 { st *head , *tail , *p; int num = 0; head = tail = p = NULL; printf...
本文件描述单向链表类模板。移植时,仅需要本文件
数据结构,c语言实现的单向链表。代码分享 struct LinkNode { int data; struct LinkNode *next; }; typedef struct LinkNode *Lnode;
C++进阶学习——单向链表的实现,相关教程链接如下: http://blog.csdn.net/tennysonsky/article/details/49685199
培训班老师自己写的单向链表,代码非常全,也很好理解,可执行。
单向链表类定义及测试文件 对应于数据机构与算法分析(c++版)第三版或第二版 作者Clifford A.Shaffer 重庆大学使用教材
这是在面试中很常见的一个例子,实现单向链表的逆转,这个例子是用递归法实现的,一个简单的单向链表的例子
c++实现单向链表逆转,c++实现单向链表逆转,c++实现单向链表逆转,c++实现单向链表逆转,c++实现单向链表逆转,
Java SE程序 类实现单向链表Java SE程序 类实现单向链表Java SE程序 类实现单向链表Java SE程序 类实现单向链表Java SE程序 类实现单向链表Java SE程序 类实现单向链表Java SE程序 类实现单向链表Java SE程序 类实现...
使用单向链表对字符串进行排序,并以从小到大的顺序显示出来。
java语言模拟单向链表,JAVA数据结构
这是近期自己参考书上和网上资源使用C++编的单向链表,主要包含了链表的增删改查功能,除此之外还有简单的排序功能,代码实现的效果图已经在项目文件夹中了,可以按照效果图进行数据的增删改查等操作,最后也希望对...
每敲一次代码都会有新的收获,基本功不扎实啥也干不了。单向链表的插入,删除,创建,遍历是数据结构的基本操作。里边的算法值得学习。下面我们就来学习一下单向链表结点的逐个删除的方法。