Java、Python中没有指针，怎么实现链表、图等数据结构？ - 知乎521被浏览76980分享邀请回答0添加评论分享收藏感谢收起Java数据结构（链表篇）
链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构，链表比较方便插入和删除操作。
package ch04L&
public class Link {&
&&& // 数据域&&
&&& // 指针域&&
&&& private L&
&&& // 构造函数&&
&&& public Link(long data) {&
&&&&&&& this.data =&
&&& public long getData() {&
&&& public void setData(long data) {&
&&&&&&& this.data =&
&&& public Link getNext() {&
&&& public void setNext(Link next) {&
&&&&&&& this.next =&
package ch04L
public class Link {
&// 数据域
&// 指针域
&private L
&// 构造函数
&public Link(long data) {
&&this.data =
&public long getData() {
&public void setData(long data) {
&&this.data =
&public Link getNext() {
&public void setNext(Link next) {
&&this.next =
测试连接点：
package ch04L&
public class TestLink {&
&&& public static void main(String[] args) {&
&&&&&&& Link link1 = new Link(10);&
&&&&&&& Link link2 = new Link(50);&
&&&&&&& Link link3 = new Link(20);&
&&&&&&& Link link4 = new Link(100);&
&&&&&&& link1.setNext(link2);&
&&&&&&& link2.setNext(link3);&
&&&&&&& link3.setNext(link4);&
&&&&&&& System.out.println(link1.getData());&
&&&&&&& System.out.println(link1.getNext().getData());&
&&&&&&& System.out.println(link1.getNext().getNext().getData());&
&&&&&&& System.out.println(link1.getNext().getNext().getNext().getData());&
package ch04L
public class TestLink {
&public static void main(String[] args) {
&&Link link1 = new Link(10);
&&Link link2 = new Link(50);
&&Link link3 = new Link(20);
&&Link link4 = new Link(100);
&&link1.setNext(link2);
&&link2.setNext(link3);
&&link3.setNext(link4);
&&System.out.println(link1.getData());
&&System.out.println(link1.getNext().getData());
&&System.out.println(link1.getNext().getNext().getData());
&&System.out.println(link1.getNext().getNext().getNext().getData());
package ch04L&
&* 链表：核心思想：链表中只包含一个数据项，即对第一个连接点的引用
&* @author hadoop
public class LinkList {&
&&& private L&
&&& // 插入&&
&&& public void insert(long value){&
&&&&&&& Link link = new Link(value);&
&&&&&&& if(first == null)&
&&&&&&&&&&& first =&
&&&&&&& else{&
&&&&&&&&&&& link.setNext(first);&
&&&&&&&&&&& first =&
&&&&&&& }&
&&& // 打印链表&&
&&& public void display(){&
&&&&&&& Link current =&
&&&&&&& while(current != null){&
&&&&&&&&&&& System.out.print(current.getData() + & &);&
&&&&&&&&&&& current = current.getNext();&
&&&&&&& }&&&&
&&& // 查询链表&&&
&&& public Link find(long key){&
&&&&&&& Link current =&
&&&&&&& while(current.getData() != key){&
&&&&&&&&&&& if(current.getNext() == null)&
&&&&&&&&&&&&&&&&
&&&&&&&&&&& current = current.getNext();&
&&&&&&& }&
&&& // 插入节点到指定位置&&
&&& public void insert(long value, int pos){&
&&&&&&& if(pos == 0)&
&&&&&&&&&&& insert(value);&
&&&&&&& else{&
&&&&&&&&&&& Link current =&
&&&&&&&&&&& for(int i = 0; i & pos - 1; i++)&
&&&&&&&&&&&&&&& current = current.getNext();&
&&&&&&&&&&& Link link = new Link(value);&
&&&&&&&&&&& link.setNext(current.getNext());&
&&&&&&&&&&& current.setNext(link);&
&&&&&&& }&
&&& // 删除节点&&
&&& public void delete(long value){&
&&&&&&& Link current =&
&&&&&&& Link ago =&
&&&&&&& while(current.getData() != value){&
&&&&&&&&&&& if(current.getNext() == null)&
&&&&&&&&&&&&&&&&
&&&&&&&&&&& else{&
&&&&&&&&&&&&&&& ago =&
&&&&&&&&&&&&&&& current = current.getNext();&
&&&&&&&&&&& }&
&&&&&&& }&
&&&&&&& if(current == first)&
&&&&&&&&&&& first = first.getNext();&
&&&&&&& else&
&&&&&&&&&&& ago.setNext(current.getNext());&
package ch04L
&* 链表：核心思想：链表中只包含一个数据项，即对第一个连接点的引用
&* @author hadoop
public class LinkList {
&private L
&public void insert(long value){
&&Link link = new Link(value);
&&if(first == null)
&&&first =
&&&link.setNext(first);
&&&first =
&// 打印链表
&public void display(){
&&Link current =
&&while(current != null){
&&&System.out.print(current.getData() + & &);
&&&current = current.getNext();
&// 查询链表
&public Link find(long key){
&&Link current =
&&while(current.getData() != key){
&&&if(current.getNext() == null)
&&&current = current.getNext();
&// 插入节点到指定位置
&public void insert(long value, int pos){
&&if(pos == 0)
&&&insert(value);
&&&Link current =
&&&for(int i = 0; i & pos - 1; i++)
&&&&current = current.getNext();
&&&Link link = new Link(value);
&&&link.setNext(current.getNext());
&&&current.setNext(link);
&// 删除节点
&public void delete(long value){
&&Link current =
&&Link ago =
&&while(current.getData() != value){
&&&if(current.getNext() == null)
&&&&current = current.getNext();
&&if(current == first)
&&&first = first.getNext();
&&&ago.setNext(current.getNext());
package ch04L&
public class TestLinkList {&
&&& public static void main(String[] args) {&
&&&&&&& LinkList linkList = new LinkList();&
&&&&&&& linkList.insert(20);&
&&&&&&& linkList.insert(80);&
&&&&&&& linkList.insert(40);&
&&&&&&& linkList.insert(60);&
&&&&&&& linkList.display();&
&&&&&&& System.out.println();&
&&&&&&& System.out.println(&找到节点，数据为：& + linkList.find(80).getData());&
&&&&&&& linkList.insert(100, 0);&
&&&&&&& linkList.display();&
&&&&&&& System.out.println();&
&&&&&&& linkList.delete(80);&
&&&&&&& linkList.display();&
package ch04L
public class TestLinkList {
&public static void main(String[] args) {
&&LinkList linkList = new LinkList();
&&linkList.insert(20);
&&linkList.insert(80);
&&linkList.insert(40);
&&linkList.insert(60);
&&linkList.display();
&&System.out.println();
&&System.out.println(&找到节点，数据为：& + linkList.find(80).getData());
&&linkList.insert(100, 0);
&&linkList.display();
&&System.out.println();
&&linkList.delete(80);
&&linkList.display();
比较链表和顺序表：
package ch04L&
import ch01Array.MyA&
public class Test {&
&&& public static void main(String[] args) {&
&&&&&&& // 构造链表&&
&&&&&&& long date1 = System.currentTimeMillis();&
&&&&&&& LinkList linkList = new LinkList();&
&&&&&&& for(int i = 0; i & 1000000; i++)&
&&&&&&&&&&& linkList.insert(i);&
&&&&&&& long date2 = System.currentTimeMillis();&
&&&&&&& System.out.println(date2 - date1);&
&&&&&&& // 构造顺序表&&
&&&&&&& long date3 = System.currentTimeMillis();&
&&&&&&& MyArray myArray = new MyArray(1000000 + 1);&
&&&&&&& for(int i = 0; i & 1000000; i++)&
&&&&&&&&&&& myArray.insert(i);&
&&&&&&& long date4 = System.currentTimeMillis();&
&&&&&&& System.out.println(date4 - date3);&
&&&&&&& // 链表删除&&
&&&&&&& long date5 = System.currentTimeMillis();&
&&&&&&& linkList.delete(60000);&
&&&&&&& long date6 = System.currentTimeMillis();&
&&&&&&& System.out.println(date6 - date5);&
&&&&&&& // 顺序表删除&&
&&&&&&& long date7 = System.currentTimeMillis();&
&&&&&&& myArray.delete(60000);&
&&&&&&& long date8 = System.currentTimeMillis();&
&&&&&&& System.out.println(date8 - date7);&链表的定义：
　　链表(linked list)是由一组被称为结点的数据元素组成的数据结构，每个结点都包含结点本身的信息和指向下一个结点的地址。由于每个结点都包含了可以链接起来的地址信息，所以用一个变量就能够访问整个结点序列。也就是说，结点包含两部分信息：一部分用于存储数据元素的值，称为信息域；另一部分用于存储下一个数据元素地址的指针，称为指针域。链表中的第一个结点的地址存储在一个单独的结点中，称为头结点或首结点。链表中的最后一个结点没有后继元素，其指针域为空。　　
如下图所示：
单链表的结构：
单链表的插入和删除示意图：
python实现代码：
#!/usr/bin/python
# -*- coding: utf-8 -*-
class Node(object):
def __init__(self,val,p=0):
self.data = val
self.next = p
class LinkList(object):
def __init__(self):
self.head = 0
def __getitem__(self, key):
if self.is_empty():
print 'linklist is empty.'
elif key &0
or key & self.getlength():
print 'the given key is error'
return self.getitem(key)
def __setitem__(self, key, value):
if self.is_empty():
print 'linklist is empty.'
elif key &0
or key & self.getlength():
print 'the given key is error'
self.delete(key)
return self.insert(key)
def initlist(self,data):
self.head = Node(data[0])
p = self.head
for i in data[1:]:
node = Node(i)
p.next = node
p = p.next
def getlength(self):
length = 0
while p!=0:
p = p.next
return length
def is_empty(self):
if self.getlength() ==0:
return True
return False
def clear(self):
self.head = 0
def append(self,item):
q = Node(item)
if self.head ==0:
self.head = q
p = self.head
while p.next!=0:
p = p.next
p.next = q
def getitem(self,index):
if self.is_empty():
print 'Linklist is empty.'
p = self.head
while p.next!=0 and j &index:
p = p.next
if j ==index:
return p.data
print 'target is not exist!'
def insert(self,index,item):
if self.is_empty() or index&0 or index &self.getlength():
print 'Linklist is empty.'
if index ==0:
q = Node(item,self.head)
self.head = q
p = self.head
= self.head
while p.next!=0 and j&index:
p = p.next
if index ==j:
q = Node(item,p)
post.next = q
q.next = p
def delete(self,index):
if self.is_empty() or index&0 or index &self.getlength():
print 'Linklist is empty.'
if index ==0:
q = Node(item,self.head)
self.head = q
p = self.head
= self.head
while p.next!=0 and j&index:
p = p.next
if index ==j:
post.next = p.next
def index(self,value):
if self.is_empty():
print 'Linklist is empty.'
p = self.head
while p.next!=0 and not p.data ==value:
p = p.next
if p.data == value:
l = LinkList()
l.initlist([1,2,3,4,5])
print l.getitem(4)
l.append(6)
print l.getitem(5)
l.insert(4,40)
print l.getitem(3)
print l.getitem(4)
print l.getitem(5)
l.delete(5)
print l.getitem(5)
l.index(5)
阅读(...) 评论()iOS safari 如何阻止“橡皮筋效果”？-土地公问答
iOS safari 如何阻止“橡皮筋效果”？
iOS safari 如何阻止“橡皮筋效果”？
&b&背景：&/b&&br&iOS 5 之后开始支持 Native Scrolling，为 Web App 带来媲美原生应用的滚动体验。使用十分方便只要在 CSS 中加入：&br&&br&&i&HTML&/i&&br&&div class=&highlight&&&pre&&code class=&language-html&&&span class=&nt&&&div&/span& &span class=&na&&class=&/span&&span class=&s&&&wrapper&&/span&&span class=&nt&&&&/span&&span class=&nt&&&div&/span& &span class=&na&&class=&/span&&span class=&s&&&scroller&&/span&&span class=&nt&&&&/span&&span class=&c&&&!-- content --&&/span&&span class=&nt&&&/div&&/span&&span class=&nt&&&/div&&/span&&/code&&/pre&&/div&&br&&i&CSS&/i&&br&&div class=&highlight&&&pre&&code class=&language-css&&&span class=&nc&&.wrapper&/span& &span class=&p&&{&/span&&span class=&k&&overflow&/span&&span class=&o&&:&/span& &span class=&k&&auto&/span&&span class=&p&&;&/span&&span class=&o&&-&/span&&span class=&n&&webkit&/span&&span class=&o&&-&/span&&span class=&k&&overflow&/span&&span class=&o&&-&/span&&span class=&n&&scrolling&/span&&span class=&o&&:&/span& &span class=&n&&touch&/span&&span class=&p&&;&/span&&span class=&p&&}&/span&&/code&&/pre&&/div&&br&但是 iOS Safari 在滑动的时候会有讨厌的 “橡皮筋效果” （Over Scroll）：&br&&br&&img src=&设计：&/b&&br&&div class=&highlight&&&pre&&code class=&language-text&&┌─────────────┐│Header│├─────────────┤│││ Scroll Area │││├─────────────┤│Footer│└─────────────┘&/code&&/pre&&/div&&br&&b&需求：&/b&&br&&ol&&li&Scroll Area 支持垂直区域滚动。&/li&&li&滑动 Header 和 Footer 不会引发全局的 “橡皮筋效果”。&/li&&li&Scroll Area 滑动到顶部或者底部，再向上或者向下拉动不会触发全局的 “橡皮筋效果”。&/li&&li&情况2 会触发 Scroll Area 局部的 “橡皮筋效果”。&/li&&/ol&背景：iOS 5 之后开始支持 Native Scrolling，为 Web App 带来媲美原生应用的滚动体验。使用十分方便只要在 CSS 中加入：HTML&div class="wrapper"&&div class="scroller"&&!-- content --&&/div&&/div&
自问自答有一个小类库可以阻止这个行为：joelambert/ScrollFix但是这是一个有限的方案：[译] 一个 iOS5 溢出滚动的（有限）修复方案 · Issue #1 · cssmagic/blog · GitHub完美解决方案： Optimizing “overflow:scroll” on iOS5 [UPDATE]HTML&div class="wrapper"&&div class="sub-wrapper"&&div class="scroller"&&!-- content --&&/div&&/div&&/div&
今晚某个项目中有类似的坑。我的业务结构如下：&!-- 顶部fixed常驻层 --&div#topfixed&!-- 中间需要-webkit-overflow-scrolling加速的层 --&div#smooth_scroll&!-- 底部fixed常驻层 --&div#bottomfixed疑难杂症需求：1. 阻止smooth_scroll的［外层］进行-webkit-overflow-scrolling2. smooth_scroll仍然保持-webkit-overflow-scrolling坑:在smooth_scroll的滚动区域到达页面顶部和底部阀值的时候，再次touchmove会直接触发原生webview的回弹效果，所以，这里需要通过判断手指上滑和下滑来屏蔽之。解决方案：function restoreEvent(ev) {var _target = ev.target,_ss = $(_target).parents().slice(-3)[0],_point = ev.touches[0],_top = _ss.scrollTop;// 什么时候到底部var _bottomFaVal = _ss.scrollHeight - _ss.offsetHeight;if(_ss.id === 'smooth_scroll'){// 到达顶端if(_top === 0) {// 阻止向下滑动if(_point.clientY & Y) {ev.preventDefault();} else {// 阻止冒泡// 正常执行ev.stopPropagation();}} else if(_top === _bottomFaVal) {// 到达底部// 阻止向上滑动if(_point.clientY & Y) {ev.preventDefault();} else {// 阻止冒泡// 正常执行ev.stopPropagation();}} else if(_top & 0 && _top & _bottomFaVal) {ev.stopPropagation();}}}
难道说，现在可以用DIV的滚动条了？
其它类似问题
其它人正在问的问题}