链结点
在链表中,每个数据项都被包含在‘点“中,一个点是某个类的对象,这个类可认叫做
LINK。因为一个链表中有许多类似的链结点,所以有必要用一个不同于链表的类来表达
链结点。每个LINK对象中都包含一个对下一个点引用的字段(通常叫做next)但是
本身的对象中有一个字段指向对第一个链结点的引用
单链表是一种顺序存取的结构,为找第i个数据元素,必须先找到第i-1个数
据元素。因此,查找第i个数据元素的基本操作为:移动指针,比较j和i
1、链接存储方法
链接方式存储的线性表简称为链表(LinkedList)。
链表的具体存储表示为:
①用一组任意的存储单元来存放线性表的结点(这组存储单元既可以是连续的,
也可以是不连续的)
②链表中结点的逻辑次序和物理次序不一定相同。为了能正确表示结点间的逻
辑关系,在存储每个结点值的同时,还必须存储指示其后继结点的地址(或位置)信
息(称为指针(pointer)或链(link))
注意:
链式存储是最常用的存储方式之一,它不仅可用来表示线性表,而且可用来表示
各种非线性的数据结构。
2、链表的结点结构
┌──┬──┐
│data│next│
└──┴──┘
data域--存放结点值的数据域
next域--存放结点的直接后继的地址(位置)的指针域(链域)
注意:
①链表通过每个结点的链域将线性表的n个结点按其逻辑顺序链接在一起的。
②每个结点只有一个链域的链表称为单链表(SingleLinkedList)。
3、头指针head和终端结点指针域的表示
单链表中每个结点的存储地址是存放在其前趋结点next域中,而开始结点无前
趋,故应设头指针head指向开始结点。
注意:
链表由头指针唯一确定,单链表可以用头指针的名字来命名。
【例】头指针名是head的链表可称为表head。
终端结点无后继,故终端结点的指针域为空,即NULL。
public class LinkList<T> {
public class Node{ //定义节点
private T data;
private Node next;
public Node(){
}
public Node(T data,Node next){
this.data=data;
this.next=next;
}
}
private Node header;//头节点
private Node tail;//尾节点
private int size;//链表大小
//构造函数初始化数据
public LinkList(){
header=null;
tail=null;
}
public LinkList(T element){
header=new Node(element,null);
tail=header;
size++;
}
//链表长度
public int length(){
return size;
}
//返回指定位置index的节点
public T get(int index){
return getNodeByIndex(index).data;
}
private Node getNodeByIndex(int index) {
if(index<0||index>size-1){
throw new IndexOutOfBoundsException("线性表索引越界");
}
Node current=header;
for(int i=0;i<size&¤t!=null;i++,current=current.next){
if(i==index){
return current;
}
}
return null;
}
//返回element在链表的位置,-1表示不存在
public int locate(T element){
Node current=header;
for(int i=0;i<size&¤t!=null;i++,current=current.next){
if(current.data==element){
return i;
}
}
return -1;
}
//在index位置插入节点element
public void insert(T element,int index){
if(index<0||index>size){
throw new IndexOutOfBoundsException("线性表索引越界");
}
if(header==null){
add(element);
}else{
if(index==0){
addAtHeader(element);
}else{
Node prev=getNodeByIndex(index-1);
prev.next=new Node(element,prev.next);
size++;
}
}
}
//采用尾插法为链表添加新节点
private void add(T element) {
// TODO Auto-generated method stub
if(header==null){
header=new Node(element,null);
tail=header;
}else{
Node newNode=new Node(element,null);
tail.next=newNode;
tail=newNode;
}
size++;
}
//采用头插法为链表添加新节点
private void addAtHeader(T element){
header=new Node(element,header);
if(tail==null){
tail=header;
}
size++;
}
//删除index位置的节点
public T delete(int index){
if(index<0||index>size-1){
throw new IndexOutOfBoundsException("线性表索引越界");
}
Node del=null;
if(index==0){
del=header;
header=header.next;
}else{
Node prev=getNodeByIndex(index-1);
del=prev.next;
prev.next=del.next;
del.next=null;
}
size--;
return del.data;
}
//从链表后面删除一个节点
public T remove(){
return delete(size-1);
}
//是否为空
public boolean empty(){
return size==0;
}
//清空链表
public void clear(){
header=null;
tail=null;
size=0;
}
public String toString(){
if(empty()){
return "[]";
}else{
StringBuilder sb=new StringBuilder("[");
for(Node current=header;current!=null;current=current.next){
sb.append(current.data.toString()+", ");
}
int len=sb.length();
return sb.delete(len-2, len).append("]").toString();
}
}
public static void main(String[] args) {
LinkList<String> list=new LinkList<String>();
list.insert("aaa", 0);
list.add("bbb");
list.add("ccc");
System.out.println(list.toString());
list.insert("ddd", 1);
System.out.println(list.toString());
list.delete(2);
System.out.println(list.toString());
System.out.println("ccc在链表中的位置:"+list.locate("ccc"));
System.out.println("链表中索引2处的元素:"+list.get(2));
}
}
分享到:
相关推荐
这是一个单向链表,它具有插入与删除节点的功能。Entry类实现了链表的各节点。
操作一个链表,链表中的节点有两个指针,一个指向下一个节点, 一个指向下下一个节点,如果下一个节点或者下下一个节点为空,则为null。 操作为插入,删除,修改。 博客:...
主要介绍了Java实现双链表互相交换任意两个节点的方法,简单讲述了双链表的概念,并结合实例形式给出了java双链表实现任意两个节点交换的操作技巧,需要的朋友可以参考下
* 基于链表实现树结构 */ package dsa; public class TreeLinkedList implements Tree { private Object element;//树根节点 private TreeLinkedList parent, firstChild, nextSibling;//父亲、长子及最大的...
* 基于位置接口实现的双向链表节点类 */ package dsa; public class DLNode implements Position { private Object element;//数据对象 private DLNode prev;//指向前驱节点 private DLNode next;//指向后继...
相信大家都明白 LinkedList 是基于双向链表而实现的,本篇文章主要讲解一下双向链表的实现,并且我们参考 LinkedList 自己实现一个单链表尝试一下。 什么是链表? 简单的来讲一下什么是链表:首先链表是一种线性的...
* 基于链表节点实现二叉树节点 */ package dsa; public class BinTreeNode implements BinTreePosition { protected Object element;//该节点中存放的对象 protected BinTreePosition parent;//父亲 ...
java语言对链表的基本操作,包括增加节点,查找结点,删除节点,更新节点四种操作
* 基于双向链表实现双端队列结构 */ package dsa; public class Deque_DLNode implements Deque { protected DLNode header;//指向头节点(哨兵) protected DLNode trailer;//指向尾节点(哨兵) protected ...
java实现双链表模拟集合练习题
* 基于链表实现二叉树 */ package dsa; public class BinTree_LinkedList implements BinTree { protected BinTreePosition root;//根节点 /**************************** 构造函数 ********************...
数据结构与算法 —— Java 实现(链表)一、单链表1.1 链表的定义1.2 链表添加一个新的节点1.3 判断当前节点是否为最后一个节点 (isLast)1.4 删除下一节点 (removeNext)1.5 显示节点信息(show)1.6 插入一个...
如果不能使用临时缓存,你怎么实现无序链表中移除重复项(?C和JAVA实例无序链表中移除重复项。
递归链表中值最大的节点.CoreJava 实现. 链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点(链表中每一个元素称为结点)组成,结点可以在...
用Java语言实现的单链表,有增加节点、删除节点、查询节点和打印链表的功能,Java和数据结构初学者的必备程序!
数据结构与算法----线性表及Java实现顺序表、链表、栈、队列 定义线性表节点的结构.pdf
java基础面试题链表中环的入口节点本资源系百度网盘分享链接
递归的方式查找链表中值最大的节点,用于交流学习。 链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点(链表中每一个元素称为结点)组成...
java链表操作的基本单元-结点类的定义,包括数据域和指针域,望大神们指点
用Java编写不带头结点的链表,是清华大学出版社,作者朱战立编写