链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
数组是连续的 线性的存储结构。
链表由一系列结点(链表中每个元素或对象称为结点)组成,结点可以在运行时动态生成。每个结点包括链各个部
分:一个是存储数据元素的数据源,另一个是存储下一个结点地址的指针域。相比于线性表顺序结构,链表比较方便插入
和删除操作。
单链表:
//单向链表结点类
public class LinkNode{
private Object obj;//结点内的数据对象
private LinkNode nextNode;//对下一个结点的引用
//构造方法 构建结点类的时候把对象传入
public LinkNode(Object obj){
this.obj = obj;
}
//返回下一个结点对象
public LinkNode getnext(){
return nextNode;
}
//设置下一个结点对象
public void setnext(LinkNode nextNode){
this.nextNode = nextNode;
}
//设置结点对象
public void setnode(Object obj){
this.obj = obj;
}
}
实现单向链表
//返回根结点
public LinkNode creatLink(){
//以字符串对象为例
String s = "根节点" ;
LinkNode root = new LinkNode(s);//根结点
LinkNode n1 = new LinkNode("一节点");
LinkNode n1 = new LinkNode("二节点");
LinkNode n1 = new LinkNode("三节点");
LinkNode n1 = new LinkNode("四节点");
root.setnext(n1);
n1.setnext(n2);
n2.setnext(n3);
n3.setnext(n4);
return root;
}
双向链表:双向式单向链表的改进 在双向链表中,结点除含有数据域外,还有两个链域,一个存储子结点地址,
一般称之为右链域;一个存储父结点地址,一般称之为左链域。
链表实现自定义队列:实现数据的插入、删除、修改、取出····
插入:将要插入位置的原结点的父结点的nextNode指向要插入的对象,再将要插入的对象的nextNode指向
原结点。(双向链表同理)
删除:将要删除位置的结点的父结点指向该位置结点的子结点。
修改:在结点类中写相应的set方法,在修改函数中直接调用。
取出:循环读取。
结点类:
public class Node {
// 节点存储的数据
private Object date;
// 上一个节点的地址
private Node privous;
// 下一个节点的地址
private Node next;
public Node() {
super();
}
// 构造函数
public Node(Object date) {
super();
this.date = date;
}
// 返回节点处的数据
public Object getDate() {
return date;
}
// 设置节点处的数据
public void setDate(Object date) {
this.date = date;
}
// 返回上一个节点
public Node getPrivous() {
return privous;
}
// 设置上一个节点
public void setPrivous(Node privous) {
this.privous = privous;
}
// 返回下一个节点
public Node getNext() {
return next;
}
// 设置上一个节点
public void setNext(Node next) {
this.next = next;
}
}
链表类:
public class LinkedList {
// 链表长度
private int size=0;
// 根节点
private Node root=null;
// 尾节点
private Node last=null;
// 构造函数
public LinkedList() {
super();
}
// 带参构造函数
public LinkedList(int size){
this.size = size;
}
// 带参构造函数
public LinkedList(int size, Node root, Node last) {
this.size = size;
this.root = root;
this.last = last;
}
// 添加节点到链表的末尾
public void add(Node node){
if(root==null){
root = node;
last = node;
}
else {
last.setNext(node);
node.setPrivous(last);
last = node;
}
size++;
}
//返会索引位置的节点
public Node get(int index){
// Node node;
if(index<0||index>=size){
return null;
}
else{
Node tnode = root;
for(int i=0;i<index;i++){
tnode = tnode.getNext();
}
return tnode;
}
}
//返回链表的长度
public int getsize(){
return size;
}
//在指索引位置插入对象
public void add(int index,Object obj){
//实例化一个新的节点对象
Node newnode =new Node(obj);
if(index==0){
root.setPrivous(newnode);
newnode.setNext(root);
root = newnode;
size++;
}
else if(index==size){
last.setNext(newnode);
newnode.setPrivous(newnode);
last = newnode;
size++;
}
else if(index<0||index>size){
System.out.println("您输入的索引位置越界了!!!");
}
else{
//得到当前位置的节点对象
Node node = this.get(index);
//得到该节点的父节点
Node pnode = node.getPrivous();
//设置父节点的下一个节点为要添加的节点
pnode.setNext(newnode);
newnode.setPrivous(pnode);
node.setPrivous(newnode);
newnode.setNext(node);
size++;
}
}
// 删除索引位置处的节点
public void delete(int index){
Node node = this.get(index);
Node pnode = node.getPrivous();
Node nnode = node.getNext();
if(pnode==null){
root = nnode;
}
else if(nnode==null){
pnode.setNext(null);
}
else{
pnode.setNext(nnode);
nnode.setPrivous(pnode);
}
size--;
}
// 删除指定的节点
public void delete(Object obj){
Node node = new Node(obj);
for(int i=0;i<this.getsize();i++){
if(this.get(i)==node){
Node nownode = this.get(i);
Node pnode = nownode.getPrivous();
Node nnode = nownode.getNext();
if(i==0){
root=nnode;
}
else if(i==this.getsize()){
pnode.setNext(null);
}
else{
pnode.setNext(nnode);
nnode.setPrivous(pnode);
}
size--;
}
}
System.out.println("您删除了"+obj);
}
// 链表排序
public void sort(){
for(int i=0;i<this.getsize();i++){
for(int j=i;j<this.getsize();j++){
Node node1 = this.get(i);
Node node2 = this.get(j);
Object date_1 = node1.getDate();
Object date_2 = node2.getDate();
int date1 = (int) node1.getDate();
int date2 = (int) node2.getDate();
if(date1>date2){
node1.setDate(date_2);
node2.setDate(date_1);
}
}
}
}//end sort
}
主函数:
import java.util.Random;
public class Manager {
/**
* @param args
*/
public static void main(String[] args) {
LinkedList ll = new LinkedList();
Node node = null;
Random ran = new Random();
for(int i=0;i<20;i++){
node = new Node();
node.setDate(ran.nextInt(50));
ll.add(node);
}
//在指定位置添加一个节点
ll.add(5, 111);
//越界添加
// ll.add(25,25);
// //删除指定索引位置的节点
// ll.delete(1);
// //删除指定的节点
// ll.delete(10);
System.out.println("排序前~~~~~~~~~~");
for(int i=0;i<ll.getsize();i++){
node = ll.get(i);
System.out.println(node.getDate());
}
System.out.println("排序后~~~~~~~~~~");
//给链表排序
ll.sort();
for(int i=0;i<ll.getsize();i++){
node = ll.get(i);
System.out.println(node.getDate());
}
}
}
分享到:
相关推荐
数据结构之链表,C#链表 数据结构之链表,C#链表 数据结构之链表,C#链表 数据结构之链表,C#链表 数据结构之链表,C#链表 数据结构之链表,C#链表
算法-数据结构之链表合并算法.rar
C通用范例源代码之数据结构之链表.pdfC通用范例源代码之数据结构之链表.pdfC通用范例源代码之数据结构之链表.pdfC通用范例源代码之数据结构之链表.pdfC通用范例源代码之数据结构之链表.pdfC通用范例源代码之数据结构...
数据结构 数据结构_使用javascript讲解数据结构之链表
C语言中数据结构之链表归并排序实例代码 问题 设有两个无头结点的单链表,头指针分别为ha,hb,链中有数据域data,链域next,两链表的数据都按递增排序存放,现要求将hb表归到ha表中,且归并后ha仍递增序,归并中...
基础数据结构之链表
线性表的存储结构使用链表。 2、提供操作:自表首插入元素、删除指定元素、搜索表中是否有指定元素、输出链表。 3、接收键盘录入的一系列整数(例10,25,8,33,60)作为节点的元素值,创建链表。输出链表内容。 4、输入...
自己写的 数据结构之链表栈与队列 出来与同路的新手分享
数据结构之链表.ppt该文档详细且完整,值得借鉴下载使用,欢迎下载使用,有问题可以第一时间联系作者~
这是一个链表的代码,它对于初学者来说是一个有很好帮助的东西,完全是自己写的,已经通过编程测试,供大家一起来分享!
1.使用Python语言实现链表数据结构 2.基于类封装思想 3.实现链表增删改查功能 4.有测试数据
数据结构顺序链表的实现数据结构顺序链表的实现数据结构顺序链表的实现数据结构顺序链表的实现数据结构顺序链表的实现数据结构顺序链表的实现
本文实例讲述了JS中的算法与数据结构之链表(Linked-list)。分享给大家供大家参考,具体如下: 链表(Linked-list) 前面我们讨论了如何使用栈、队列进行存数数据,他们其实都是列表的一种,底层存储的数据的数据结构都...
单链表 单循环链表 双链表 双循环链表 内容学习于 https://www.bilibili.com/video/BV1W64y1z7jh?p=19&spm_id_from=pageDriver&vd_source=4d33bf4ac4499f2c0370694554a02fa5
主要是针对c++中的链表模版进行了实现,希望可以帮助需要的人
C++数据结构之链表的创建 前言 1.链表在C/C++里使用非常频繁, 因为它非常使用, 可作为天然的可变数组. push到末尾时对前面的链表项不影响. 反观C数组和std::vector, 一个是静态大小, 一个是增加多了会对之前的元素...
list v2 用Object对象,接口inteface,迭代器Iterator实现linklist,Arraylist